백준 / 2667 / 단지번호붙이기 (그래프, dfs)

direction = [[1,0], [-1,0], [0,1], [0,-1]]

def dfs(x,y, deph, idx):
    visited[x][y] = True
    
    result[idx] += 1

    for d in direction:
        nx, ny = x+d[0], y +d[1]
        if 0 <= nx < n and 0 <= ny < n and maps[nx][ny] == 1:
            if not visited[nx][ny]:
                visited[nx][ny] = True
                dfs(nx, ny, deph+1, idx)

n = int(input())
maps = [[0] * n for _ in range(n)]

for i in range(n):
    maps[i] = list(map(int, input()))

visited = [[False]*n for _ in range(n)]
result = []
idx = 0
for x in range(n):
    for y in range(n):
        if maps[x][y] == 1 and not visited[x][y]:
            result.append(0)
            dfs(x,y, 0, idx)
            idx += 1

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

DFS를 사용해 푼 문제

주어진 지도를 2중 for문을 통해 돌면서 1을 찾으면 dfs 진행

1을 찾기으면 result에 0을 append 해서 추가된 0을 dfs 진행 시 +1 해주면서 크기를 저장한다.

visited를 통해서 방문 여부를 체크하는 것이 중요하다.