백준 2665번 미로 만들기 풀러 가기

문제 설명

구현 아이디어

처음 문제를 읽었을 때는 전에 풀었던 연구소 문제가 떠올라서 백트래킹 + BFS가 생각났다.
하지만 연구소 문제와 달리 바꾸어야 할 방의 개수가 정해지지 않았기 때문에 백트래킹을 사용하더라도 바꾸어야 할 방의 개수를 1부터 n까지 다 해보아야 하기 때문에 좋지 않은 풀이라고 생각했다.

더불어 이번 스터디 주제가 최단 경로인데, 이 문제에 최단 경로를 어떻게 접목해야 할지 몰라 결국 다른 사람의 풀이를 참고하였다 🥹

다익스트라의 개념 + BFS를 합친 문제이다.
( 여기서 비용은 흰 방으로 바꿔야 하는 검은 방의 개수를 의미한다. )
1. 출발 위치를 기준으로 인접한 위치를 먼저 방문한다.
2. 상하좌우로 탐색한다. (이 때 다음 위치는 맵을 벗어나지 않고, 방문하지 않은 곳이어야 한다.)
3-1. 방문한 곳이 검은 방이라면, 현재의 비용에 +1을 하여 힙에 저장한다.
3-2. 방문한 곳이 검은 방이 아니라면, 현재의 비용을 그대로 힙에 저장한다.
4. 현재 위치가 도착지일 때는 현재의 비용을 반환하도록 한다.

우선순위 큐를 사용했을 때 원소를 pop하면, 작은 값이 먼저 반환되므로 검은 방이 아닌 곳을 방문하려고 하고, 만약 모두 방문했을 때 검은 방이 아닌 곳을 방문하게 된다.

전체 코드

import sys
import heapq

input = sys.stdin.readline

n = int(input())
graph = []

for _ in range(n):
    graph.append(list(input().rstrip()))

def dijkstra(a, b):
    hq = []
    dx = [0, 1, 0, -1]
    dy = [-1, 0, 1, 0]
    visited = [[False for _ in range(n)] for _ in range(n)]

    visited[a][b] = True
    heapq.heappush(hq, (0, a, b))

    while hq:
        weight, x, y = heapq.heappop(hq)
        if x == n-1 and y == n-1:
            return weight

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

            if nx < 0 or ny < 0 or nx >= n or ny >= n or visited[nx][ny]:
                continue
            visited[nx][ny] = True
            if graph[nx][ny] == '1':
                heapq.heappush(hq, (weight, nx, ny))
            else:
                heapq.heappush(hq, (weight+1, nx, ny))

answer = dijkstra(0, 0)
print(answer)

비슷한 문제를 더 풀고 싶다면 ...

비슷한 문제로는 백준 1261번 알고스팟이 있다.