백준 / 단지번호붙이기 / 2667
Question
문제링크
Silver 1
Logic
기본 구조 : bfs
1. 상하좌우를 탐색하기 위해 dx, dy를 선언한다.
2. 기본적으로 1로 표시되어있는 초기 그래프를 탐색하며, 1을 마주친다면 bfs를 실행시킨다.
3. 그래프의 범위 내에서, 1과 붙어있는 다음 1을 탐색하고, 갯수를 센다.
4. 이 과정을 모두 마치면, 각 단지 별 집의 수를 오름차순으로 출력한다.
Code
from collections import deque
dx = [-1,0,0,1]
dy = [0,1,-1,0]
def bfs(a,b):
global li
n=len(li)
queue = deque()
queue.append([a,b])
li[a][b] = 0
count=1
while queue:
x,y = queue.popleft()
for i in range(4):
xx = x+dx[i]
yy = y+dy[i]
if xx < 0 or xx >= n or yy < 0 or yy >= n: continue
if li[xx][yy] == 1:
li[xx][yy]=0
queue.append([xx,yy])
count+=1
return count
li=[]
N=int(input())
for _ in range(N):
li.append(list([int(i) for i in [*input()]]))
cnt=[]
for i in range(N):
for j in range(N):
if li[i][j]==1:
cnt.append(bfs(i,j))
cnt.sort()
print(len(cnt))
for _ in range(len(cnt)): print(cnt[_])
Author And Source
이 문제에 관하여(백준 / 단지번호붙이기 / 2667), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@swany0509/백준-단지번호붙이기-2667저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)