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

문제설명
지도를 입력받고 인접한 주택들끼리를 단지로 묶어서 단지의 개수와 단지별 주택의 개수를 오름차순으로 출력하는 문제입니다.

작동 순서
1. 지도의 크기를 입력받습니다.
2. 지도를 입력받습니다.
3. 맵전체를 확인하며 방문한적이 없는 주택이 있을 경우 그 주택을 시작으로 탐색을 시작하고 단지번호를 지정합니다.
4. 상하좌우로 인접한 곳에 주택이 있을 경우 그 주택도 같은 단지에 넣어줍니다.
5. 주택 단지를 모두 나누고 난 뒤에 단지별로 주택이 몇개씩 있는지를 확인합니다.
6. 단지의 개수와 단지별 주택수를 오름차순으로 정렬한뒤 출력합니다.

소스코드

import sys
from collections import deque
N = int(sys.stdin.readline())
townMap = []
visited = [[False for _ in range(N)]for _ in range(N)]
move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
q = deque()
estate = 0

for i in range(N):
    townMap.append(list(map(int, sys.stdin.readline().rstrip())))

for i in range(N):
    for j in range(N):
        if not visited[i][j] and townMap[i][j] == 1:
            q.append([i, j])
            estate += 1
        while q:
            x, y = q.popleft()
            townMap[x][y] = estate
            for m in range(4):
                if N > x+move[m][0] >= 0 and N > y+move[m][1] >= 0:
                    if townMap[x+move[m][0]][y+move[m][1]] == 1 and not visited[x+move[m][0]][y+move[m][1]]:
                        visited[x+move[m][0]][y+move[m][1]] = True
                        q.append([x+move[m][0], y+move[m][1]])

print(estate)
count = [0 for i in range(estate)]
for i in range(N):
    for j in range(N):
        if townMap[i][j] != 0:
            count[townMap[i][j]-1] += 1
count.sort()
for i in count:
    print(i)