[BOJ/백준] 2667 단지번호붙이기 (Python 파이썬)

알고리즘 문제 풀이 첫 포스팅입니다..! 알고리즘 문제를 풀기 시작한 지 얼마 안 되었을 때는, 쉬운 문제임에도 오랜 시간이 걸렸고 대부분 문제 풀이에 실패했었는데요, 이제는 어느정도 익숙해 지면서 성공하는 문제도 늘어나면서 문제를 이해하고 어떤 알고리즘을 써야할 지 대충 보이기 시작했습니다. 이제는 슬슬 내가 풀었던 문제들을 알고리즘 별로 정리하면서 숙달할 필요가 있겠다고 생각하여 포스팅을 시작하게 되었습니다.
방학동안 알고리즘 공부에 대한 목표가 있는데, 1. 기본 자료구조 및 알고리즘 기계적으로 나올 때 까지 숙달, 2. 기본 문제 유형 파악, 분석하고 연습하기, 이렇게 두 가지입니다. 백준 티어 오르는 것을 보면서 소소하게 동기부여를 받으며 공부하고 있습니다.. :)
프로젝트와 다른 공부도 병행하면서 매일 매일 꾸준히 푸는 것이 목표입니다!

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

문제 풀이

저는 BFS로 풀이를 진행하였습니다. 다 풀고 다른 분들의 풀이를 보니 DFS와 재귀를 이용하신 분들도 계셨는데, 둘 다 좋은 풀이인 것 같습니다..!
BFS 풀이들은 제 코드랑 거의 비슷했습니다.
이 문제처럼 미로가 등장할 때는 항상 dx, dy를 선언하여 이동 방향을 설정하는 것이 풀이에 도움이 됩니다. for문을 통해 4가지 방향에 대해서 다음 좌표를 구하고, 미로 조건을 검사하는 방식으로 탐색하는 것입니다. 이때 queue를 사용하여 BFS를 구현했습니다.

문제는, 다음 단지로 어떻게 향해서 다시 BFS를 실시할 것인가이었는데, 문제 조건을 살펴보면 "5≤N≤25" 입니다.

그렇다면, 그래프의 모든 노드를 2중 for문으로 하나씩 돌아봤자 cost가 매우 작기 때문에 time complexity는 무의미하다고 판단하여 각 좌표를 하나씩 검사하여 만약 방문하지 않았다면 BFS를 실시하도록 했습니다.

풀이

import sys
from collections import deque
input = sys.stdin.readline
ans = []

# graph, visited
N = int(input())
graph = [list(map(int, ' '.join(input().split()))) for _ in range(N)]


# 이동 방향 : 위, 아래, 왼쪽, 오른쪽
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def BFS(a, b):
    queue = deque([(a, b)])

    # graph[i][j] == 1인 i,j에서 시작하므로
    graph[a][b] = 0
    cnt = 1

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if graph[nx][ny] == 1:
                    queue.append((nx, ny))
                    graph[nx][ny] = 0 #visited 대신 graph 좌표를 0으로 바꿔서 solve에서 걸리지 않도록
                    cnt += 1
    if cnt != 0:
        ans.append(cnt)

def solve():
    for i in range(N):
        for j in range(N):
            if graph[i][j] == 1:
                BFS(i, j)

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

처음 풀이에서는 visited 리스트를 만들어서 0으로 모두 초기화 한 뒤에 방문할 때 마다 해당 자리를 1로 바꿔주는 방식을 사용했습니다만, 주어진 예제 입력은 잘 통과가 되는데 정답처리가 되지 않았습니다. 수정을 거칠 수록 코드가 난잡해져서 결국은 visited를 없애고 solve에서 graph가 1인 구간만 BFS를 호출하고, BFS에서는 방문한 graph 자리는 0으로 바꿈으로써 재방문을 방지했습니다.

다른 분들의 풀이를 보니 방문한 자리를 0으로 바꾸는 것이 결국은 정답이었네요.
아직은 그래프 탐색이 익숙치 않아 풀이가 오래 걸렸는데 이 문제를 품으로써 조금은 숙달된 것 같습니다!