[백준 2665] 미로 만들기

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

2665번: 미로만들기

---

접근

다익스트라의 주요 개념을 이해하는데 도움이 되었다. (1, 1)에서 출발하여 (N, N)에 도착할 때의 비용을 구해야한다. 벽을 부시는 것을 비용이라고 한다. 기본적으로 현재의 위치를 기준으로 상하좌우를 탐색한다. 이어서 벽일 때는 현재의 비용에서 +1, 벽이 아닐 때는 현재의 비용을 그대로 힙에 추가한다. 

 

그렇다면 힙은 비용을 기준으로 다음 탐색할 위치가 나오게된다. 여기서 이미 벽을 부시고 비용이 1이된 상태에서 다음 위치를 확인하려했을 때 벽을 부시지않고 이동할 수 있는 위치가 있을 수 있다. 이때는 0이 아닌 그대로 비용 1이 된다. 이러한 문제를 방지하기 위해 방문표시를 하게되고 결론적으로 벽이 아닌 곳을 계속해서 방문하게되고 이를 모두 방문했을 때는 벽이 위치한 곳을 방문하게 된다.

 

다익스트라는 하나의 위치에서 다른 모든 위치까지의 최소비용거리를 구하는 것이며 이를 위해 메모제이션을 활용하고 이전까지의 최소비용을 통해 다음 비용을 구하게된다. 

 

구현

- 출발위치를 기준으로 인접한 위치를 먼저 방문한다.

- 상하좌우를 탐색하여 다음 위치를 탐색하는데 맵을 벗어나지 않고 방문하지 않은 곳이어야 한다.

- 방문한 곳이 벽이라면 현재의 비용에서 + 1을 하여 힙에 저장하고 그렇지 않을 때는 현재의 비용을 그대로 힙에 저장한다.

- 그렇다면 힙을 통해 계속해서 최소비용을 갖는 다음 탐색 위치가 나오게된다.

- 이제 현재 위치가 도착지일 때는 현재의 비용을 반환하도록 한다.

def dijkstra(y, x):
    hq = []
    dy = [1, -1, 0, 0]
    dx = [0, 0, 1, -1]
    visited = [[0 for _ in range(N)] for _ in range(N)]

    heapq.heappush(hq, (0, y, x))
    visited[y][x] = 1
    while hq:
        weight, cy, cx = heapq.heappop(hq)
        if cy == N-1 and cx == N-1:
            return weight

        for d in range(4):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if check_range(ny, nx) and visited[ny][nx] == 0:
                visited[ny][nx] = 1
                if board[ny][nx]:
                    heapq.heappush(hq, (weight, ny, nx))
                else:
                    heapq.heappush(hq, (weight + 1, ny, nx))

---

전체 코드

import heapq

def check_range(y, x):
    return (0 <= y < N) and (0 <= x < N)

def dijkstra(y, x):
    hq = []
    dy = [1, -1, 0, 0]
    dx = [0, 0, 1, -1]
    visited = [[0 for _ in range(N)] for _ in range(N)]

    heapq.heappush(hq, (0, y, x))
    visited[y][x] = 1
    while hq:
        weight, cy, cx = heapq.heappop(hq)
        if cy == N-1 and cx == N-1:
            return weight

        for d in range(4):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if check_range(ny, nx) and visited[ny][nx] == 0:
                visited[ny][nx] = 1
                if board[ny][nx]:
                    heapq.heappush(hq, (weight, ny, nx))
                else:
                    heapq.heappush(hq, (weight + 1, ny, nx))

N = int(input())
board = []
for _ in range(N):
    board.append(list(map(int, input().strip())))
answer = dijkstra(0, 0)
print(answer)