백준, 단지번호붙이기, 2667, 파이썬

[유형]

dfs

 

[문제링크]

https://www.acmicpc.net/problem/2667

 

[요약]

철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

 

[문제풀이]

import sys
# sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline().rstrip()
def dfs(x, y):
    global count

    if x < 0 or x >= n or y < 0 or y >= n:
        return

    if graph[x][y] == 1:
        count += 1
        graph[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            dfs(nx, ny)



graph = []
result = []
count = 0
dx = [0,0,1,-1]
dy = [1,-1,0,0]

n = int(input())

for _ in range(n):
    graph.append(list(map(int, input())))
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            dfs(i,j)
            result.append(count)
            count = 0

result.sort()
print(len(result))

for k in result:
    print(k)