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

문제 : www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

풀이

너비 우선 탐색으로 해결하였다.

모든 위치를 한번씩 방문하고 해당 위치에 집이 있을 경우(==1) 큐에 추가한다.

while que에서 상하좌우 중 집이 있을 경우 큐에 추가한다.

큐에 추가를 할때 마다 k + 1을 해주고, 큐가 끝나면 num리스트에 k값(단지당 집의 개수)을 추가한다.

최종적으로 num리스트의 길이와 정렬된 num을 출력한다.

 

N = int(input())
house = []
for i in range(N):
    temp = list(map(int, input()))
    house.append(temp)

num = []
que = deque()
xx = [-1,1,0,0]
yy = [0,0,-1,1]

for x in range(N):
    for y in range(N):
        k = 0
        
        if house[x][y] == 1:
            que.append((x,y))
            house[x][y] = 0
            k += 1
            
        while que:
            i, j = que.popleft()
            for a in range(4):
                if 0<=i+xx[a]<N and 0<=j+yy[a]<N and house[i+xx[a]][j+yy[a]] == 1:
                    que.append((i+xx[a],j+yy[a]))
                    house[i+xx[a]][j+yy[a]] = 0
                    k += 1

        if k != 0:
            num.append(k)

print(len(num))
num.sort()
for i in num:
    print(i)