[PS] BOJ 2665 / 미로만들기

Minjun Kim

19 Sep 2025 • 4 min read

Thumbnail: Photo by Danist Soh (Unsplash)

문제 링크: https://www.acmicpc.net/problem/2665

우선순위 큐를 활용한 BFS로 최단 거리를 찾는 문제입니다.

풀이

1) 우선순위 큐 기반 BFS

격자 그래프의 각 칸은 흰 방(1)이거나 검은 방(0)입니다. 흰 방만 통과할 수 있으며, 검은 방을 지나가려면 먼저 그 칸을 흰 방으로 바꾼 뒤 지나가야 합니다.

$(1, 1)$부터 $(N, N)$까지 가는 경로 중에서 검은 방을 바꾸는 경우를 찾아야 합니다. 따라서, 최단 거리의 "거리"는 지나간 경로에서 만난 검은 방의 개수가 됩니다.

너비 우선 탐색(BFS)로 격자 그래프를 탐색하는데, 그냥 큐를 사용하는 것 보다 우선순위 큐를 사용하는 것이 더 효율적입니다. 최단 거리를 구해야 하기 때문에, 거리가 더 짧은 정점을 먼저 방문하는 것이 낫기 때문입니다.

입력 그래프 전처리

입력 그래프에는 흰 방이 1, 검은 방이 0으로 표현됩니다. 파이썬의 우선순위 큐는 최소 힙으로 구현되어 있으므로 (가중치가 작을수록 더 먼저 큐에서 제거됩니다) 거리가 더 작은 정점을 먼저 꺼내게 됩니다.

앞서 문제의 정의에 따라, 거리를 "지금까지 지나온 검은 방의 개수"로 정의했습니다. 이 경우, 검은 방을 1, 흰 방을 0으로 두는게 계산에 편리하다 생각했습니다.

따라서, 입력 그래프의 0을 1로, 1을 0으로 바꿔서 저장했습니다.

# 구현의 편의를 위해, 흰 방을 0으로 두고 검은 방을 1로 둔다 (입력을 반전시킴)
room = list(list(map(lambda x: 1 - int(x), input().rstrip())) for _ in range(N))

# 위 코드는 아래 코드와 같습니다.
room = [[0 for _ in range(N)] for _ in range(N)]
for r in range(N):
  for c, tile in enumerate(map(int, input().rstrip())):
      room[r][c] = 1 - tile

입력 그래프 전처리하기

우선순위 큐 기반 BFS 구현하기

앞서 전처리를 통해 격자 그래프에서 흰 방이 0, 검은 방이 1로 표현되도록 했습니다.
이를 통해, 현재 정점까지의 거리는 그냥 격자 그래프 상에 저장된 값을 바로 더해서 사용할 수 있습니다.

MAX = N * N # 탐색하지 않은 정점의 거리를 나타내는 값.
DIFF = ((-1, 0), (1, 0), (0, -1), (0, 1)) # 다음에 방문할 정점의 위치를 계산하기 위한 배열

visited = [[False] * N for _ in range(N)] # 방문 여부를 기록할 배열
distance = [[MAX] * N for _ in range(N)] # 거리를 기록할 배열
distance[0][0] = 0
# 우선순위 큐
queue = []
heappush(queue, (0, 0, 0))

while queue:
    cost, r, c = heappop(queue)
    for dr, dc in DIFF:
        nr = r + dr
        nc = c + dc
        if 0 <= nr < N and 0 <= nc < N and not visited[nr][nc]:
            visited[nr][nc] = True
            new_dist = cost + room[nr][nc] # 검은 방이면 1 증가, 그렇지 않으면 이전 거리와 동일
            if new_dist < distance[nr][nc]:
                distance[nr][nc] = new_dist
                heappush(queue, (new_dist, nr, nc))

print(distance[N-1][N-1])

우선순위 큐 기반 BFS

전체 코드

from heapq import heappop, heappush
input = open(0).readline
N = int(input())

# 구현의 편의를 위해, 흰 방을 0으로 두고 검은 방을 1로 둔다 (입력을 반전시킴)
room = list(list(map(lambda x: 1 - int(x), input().rstrip())) for _ in range(N))

MAX = N * N
DIFF = ((-1, 0), (1, 0), (0, -1), (0, 1))
visited = [[False] * N for _ in range(N)]
distance = [[MAX] * N for _ in range(N)]
distance[0][0] = 0
queue = []
heappush(queue, (0, 0, 0))

while queue:
    cost, r, c = heappop(queue)
    for dr, dc in DIFF:
        nr = r + dr
        nc = c + dc
        if 0 <= nr < N and 0 <= nc < N and not visited[nr][nc]:
            visited[nr][nc] = True
            new_dist = cost + room[nr][nc] # 검은 방이면 1 증가, 그렇지 않으면 이전 거리와 동일
            if new_dist < distance[nr][nc]:
                distance[nr][nc] = new_dist
                heappush(queue, (new_dist, nr, nc))

print(distance[N-1][N-1])

solution.py