[BOJ] 2667 : 단지번호붙이기 - 파이썬(Python)

문제 해석

---

 

 

BFS나 DFS를 이용해서 1인 구역의 갯수와 해당 구역의 1의 수를 구하는 문제이다.

 

이 문제는 저번에 DFS/BFS를 정리하면서 풀었던 예제 아이스크림 얼려 먹기 문제와 미로 탈출 문제를 합친 것 같았다.

 

그래서 처음엔 그 두 문제의 풀이법을 그대로 섞어서 사용하면 답이 나올 것으로 생각했다.

 

문제 풀이

---

두 풀이법의 혼용이라 함은

for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            apart.append(BFS(i, j))

함수의 호출부분이 모든 그래프의 노드를 훑으면서 탐색을 시작할 수 있는 노드를 찾는 방식으로 탐색이 이루어진 구역의 수를 찾는 아이스크림 얼려 먹기 문제의 방식과

 

            if graph[nx][ny] == 0:
                continue

            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                deq.append((nx, ny))
    return graph[N - 1][N - 1]

 

다음 노드에 이전 노드 값 + 1을 저장하면서 나아가는 미로 탈출 문제의 BFS 방식을 혼용하면 될 것이라고 생각했으나

 

이 문제는 특정 인덱스의 노드가 가진 값을 찾는 문제가 아니고 탐색이 한 구역에서 몇번 일어났는지 그 횟수를 구하는 문제이기 때문에 BFS를 구현하는 부분을 다르게 해야했다.

 

 

import sys
from collections import deque


def BFS(x, y):

    deq = deque()
    deq.append((x, y))
    graph[x][y] = 0
    cnt = 1
    while deq:
        x, y = deq.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= N or ny >= N:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = 0
                deq.append((nx, ny))
                cnt += 1
    return cnt


N = int(sys.stdin.readline().rstrip())

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

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

apart = []


result = 0

for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            apart.append(BFS(i, j))
apart.sort()
print(len(apart))
for a in apart:
    print(a)

 

이렇게 한 구역의 탐색이 진행되는 동안 변수 cnt를 1씩 증가시키면서 한 단지에 아파트 수가 몇개인지를 구하고 리스트 apart에 append 시킨다.

 

리스트 apart의 길이가 단지의 수이다.