백준 2667

0과 1로 구성된 n X n 크기의 지도가 주어질 때,
연속된 1의 묶음 수(단지 수)와 각 묶음에 포함된 1의 개수(집 수)를 구하는 문제이다.

전형적인 그래프 탐색 문제라고 생각했고 DFS로 풀었다.

주의할 점이 있다면..
1) 문자열은 변경 불가(immutable)하므로 graph에 저장되는 값을 정수형으로 변환한다.
2) 각 단지의 집 수를 구할 때 해당 변수를 전역 변수로 선언해야 한다.

코드(정답)는 다음과 같다.

# 2667

import sys
sys.setrecursionlimit(10000)

def dfs(x, y):
    # 1. 좌표가 범위를 벗어나는 경우
    if x <= -1 or x >= n or y <= -1 or y >= n:
        return False

    # 2. 좌표가 범위를 벗어나지 않는 경우
    # 2-1. 해당 위치에 집이 있는 경우
    if graph[x][y] == 1:
        graph[x][y] = 0

        global part
        part += 1
        
        dfs(x - 1, y)
        dfs(x + 1, y)
        dfs(x, y - 1)
        dfs(x, y + 1)

        return True

    # 2-2. 해당 위치에 집이 없는 경우
    return False


n = int(sys.stdin.readline())

graph = []
for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().rstrip())))

# 지도 탐색(DFS)
whole = 0
parts = []
part = 0
for i in range(n):
    for j in range(n):
        if dfs(j, i):
            whole += 1

            parts.append(part)
            part = 0

# 결과 출력
print(whole)
parts.sort()
for part in parts:
    print(part)