[PS] DFS/BFS: 2667 단지번호붙이기

문제 출처

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

code

def dfs(x, y):
    # 현재 위치가 지도 내에 있고, 집(1)이 있는 경우 탐색 진행
    if x < 0 or x >= N or y < 0 or y >= N or graph[x][y] == 0:
        return 0

    # 현재 위치를 방문 처리(집을 센다)
    graph[x][y] = 0
    count = 1

    # 상, 하, 좌, 우 방향으로 집을 탐색
    count += dfs(x - 1, y)
    count += dfs(x + 1, y)
    count += dfs(x, y - 1)
    count += dfs(x, y + 1)

    return count


# 입력 받기
N = int(input())
graph = []
for _ in range(N):
    graph.append(list(map(int, input().strip())))

# 단지 수와 각 단지의 크기를 저장할 리스트
complex_sizes = []

# 모든 위치를 탐색
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:  # 집이 있는 경우 새로운 단지를 발견
            complex_size = dfs(i, j)
            complex_sizes.append(complex_size)

# 결과 출력
complex_sizes.sort()
print(len(complex_sizes))
for size in complex_sizes:
    print(size)