백준 / 단지번호붙이기 / 2667

박성완·2022년 3월 31일
0

백준

목록 보기
45/78
post-thumbnail

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[_])

0개의 댓글