[BOJ] 2667번 : 단지 번호 붙이기

 

📌 풀이

이 문제는 어디서부터 시작해야하는 지 나와있지 않기 때문에, NxN을 모두 다 돌 수 있도록 BFS로 풀었다. DFS로 풀어도 풀리지만 BFS로 푼 문제가 몇 개 없어서 그냥 BFS로 풀어봤다. 시간이 나면 DFS로도 풀어봐야겠다.

그래프에서 상하좌우로 이동할건데, 0행, N-1행, 0열, N-1열만 다르게 조건을 주기 싫어서 padding을 넣었다. 그래서 NxN가 아니라 (N+2)x(N+2) 그래프리고 패딩값들은 모두 0으로 채워넣었다.

문제에서 주어지는 값들을 graph에 저장하고, 만약 1이라면 BFS를 실시하고, 아니면 그냥 넘어가도록 했다.

bfs에서도, 현재 위치에서 갈 수 있는 좌표들을 queue에 넣어놓고, queue가 다 빌 때까지 탐색을 진행하여 단지에 속하는 집의 수를 return 하도록했다.

ans에 각 bfs를 실행한 값을 저장한다.

그럼 ans의 인덱스 수가 단지 수 이고, 각각의 값들이 단지에 속하는 집의 수가 된다.

🔑 python 코드

# 단지번호붙이기
from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N = int(input())
graph = [[0 for _ in range(N + 2)] for _ in range(N + 2)]
ans = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for i in range(1, N + 1):
    temp = input()
    for j in range(1, N + 1):
        graph[i][j] = int(temp[j - 1])

def bfs(a, b):
    queue = deque()
    queue.append((a, b))
    graph[a][b] = 0 #한번 탐색한 것은 다시 방문하지 않도록
    cnt = 1

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx, ny))
                cnt += 1

    return cnt

for i in range(1, N + 1):
    for j in range(1, N + 1):
        if graph[i][j] == 1:
            ans.append(bfs(i, j))

ans.sort()
print(len(ans))
for i in range(len(ans)):
    print(ans[i])