백준 2667번: 단지 번호 붙이기 [python]

난이도 : 실버 1
유형 : BFS or DFS (여기선 내가 더 약한 BFS로 풀었다.)

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

문제 접근

BFS로 풀려고 했는데, 우선 해당 문제는 노드, 간선 이 주어지지 않고 0,1 로 이루어진 행렬의 형태로 주어져있다.

이 경우는 내가 항상 풀던 인접 리스트 방식이 아닌 인정 행렬 방식으로 풀어야 한다.

• 2차원 리스트를 인접 행렬로 사용해 그래프 표현
• dx, dy라는 방향 벡터로 상하좌우를 간결하게 탐색
• 방문한 노드는 0으로 바꿔 재방문 방지

해답 및 풀이

import sys
from collections import deque

input = sys.stdin.readline

# 1. 입력
N = int(input())

graph = []
for i in range(N):
    house = input().strip()
    graph.append(list(map(int,house)))

# 2. 방향 벡터 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    queue = deque()
    queue.append((x,y))
    graph[x][y] = 0 # 탐색한 위치를 0으로 바꿔 다시 방문하지 않게 처리.
    count = 1

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

        for d in range(4): # d를 기준으로 상 하 좌 우 움직인 네번의 경우
            nx = x + dx[d]
            ny = y + dy[d]

            # 4방향 범위 내에 있고, 집(1)이면 
            if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] == 1:
                graph[nx][ny] = 0 # 방문 처리
                queue.append((nx,ny))
                count += 1
    
    return count

# 단지 탐색
result = []
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            result.append(bfs(i, j))

# 결과 출력
print(len(result))
for r in sorted(result):
    print(r)

항상 인접 리스트 방식만 써보다가, 2차원 리스트 + 방향 벡터로 푸니까 낯설어서 어렵게 느껴진다

다음에 떠올려야할 포인트들

1. 그래프 탐색이구나
2. 연결된 덩어리를 세어야 하네 → DFS/BFS 중 하나 써야겠다.
3. 방문 여부 체크 필수
4. 좌표 탐색이니까 dx/dy로 상하좌우 움직이자.
5. 탐색할 때 카운트 세서 리스트에 저장