1261 알고스팟 그래프

골4

다익스트라 알고리즘과 bfs 알고리즘 두가지 방법으로 모두 풀 수 있었다.

다만 나는 지금 다익스트라 알고리즘을 공부 중이므로 다익스트라로 풀었다.

bfs

bfs 로 푸는 방식은 그리디하게 풀게 된다.

1. deque 을 만들어 앞 뒤 푸쉬를 가능하게 한다.
2. 먼저 벽을 뚫지 않고 가는 길을 모두 탐색한다.
   2-1 이 방법은 4방향 노드를 탐색하면서 0인 노드는 queue 의 앞에 넣고, 1인 노드는 뒤에 넣는다.
   이렇게 하면 해당 코드는 0인 노드를 모두 탐색하고 1인 노드 탐색을 시작한다.
   즉, 0인 노드를 모두 탐색하고 1인 노드를 탐색하면 최소의 벽을 부실 수 있다는 것을 보장하는 것이다.
3. N, M 까지 모두 탐색해서 노드가 N, M 이 되면 출력한다.

개인적으로 실제로 테스트를 볼 때는 위험한 방식일 수 있겠다는 생각이 든다. 내가 생각하지 못했던 부분을 간과하고 그리디하게 풀었다가 낭패를 볼 수 있다.

다익스트라

처음 문제를 봤을 때는 다익스트라를 생각하기 힘들 수 있다. 왜냐면 골드 이하의 다익스트라 문제는 항상 노드/간선 형태로 문제가 주어졌기 때문이다.

하지만 좌표에서도 다익스트라 알고리즘을 이용해 최소 경로를 찾아낼 수 있다.

좌표에서 상하좌우로 이동한다면 상하좌우의 간선이 존재한다고 생각하면 된다.

이 부분에서 조금만 다르게 생각한다면 다익스트라로 풀 수 있다.

또 다른 점은 2차원 좌표로 문제가 주어졌기 때문에, distance 결과 배열 또한 2차원 배열로 만들어주어야 한다는 것이다.

해당 부분을 주의하면서 다익스트라 알고리즘을 응용하면 쉽게 풀린다.

import heapq
INF = int(1e9)
M, N = map(int, input().split(" "))

graph = [list(map(int, input())) for _ in range(N)]
q = []
distance = [[INF for _ in range(M)] for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def solution():

    dijkstra((0,0))


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


def dijkstra(start):
    heapq.heappush(q, (0, start))
    distance[start[1]][start[0]] = 0

    while q:
        dist, now = heapq.heappop(q)

        if distance[now[1]][now[0]] < dist:
            continue
        for i in range(4):
            nx = now[0] + dx[i]
            ny = now[1] + dy[i]
            if nx < 0 or ny < 0 or nx >= M or ny >= N:
                continue
            else:
                cost = dist + graph[ny][nx]
                if cost < distance[ny][nx]:
                    distance[ny][nx] = cost
                    heapq.heappush(q, (cost, (nx, ny)))
solution()