[Baekjoon 1261] 알고스팟

문제

💛Ⅳ [Baekjoon 1261 - 알고스팟]

문제 풀이 방법

(1, 1) 부터 (N, M)까지의 최단거리를 구하는 문제이므로 다익스트라 알고리즘 문제이다. 하지만 노드와 간선으로 연결된 그래프 형태가 아닌 2차원 배열 형태이므로 약간의 변형이 필요하다. 2차원 배열 탐색은 BFS 탐색 방법으로 풀이하였다.

1. graph와 distance 배열을 초기화한다.
2. 다익스트라 알고리즘을 수행한다.
   1. (거리, 노드) 대신 [x,y]를 큐에 삽입한다.
   2. 노드에 연결된 간선 대신 좌표의 상하좌우를 탐색한다.
   3. 거리 대신 좌표의 값을 cost로 계산한다.

풀이 코드

Python

import sys, heapq
input = sys.stdin.readline

INF = int(1e9)
M, N = map(int, input().split())
graph = [input().rstrip() for _ in range(N)]
distance = [[INF]*M for _ in range(N)]

# 이동할 네 방향 정의
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dijkstra(start):
    q = []
    heapq.heappush(q, (0,start))
    distance[start[0]][start[1]] = 0
    while q:
        dist, [x,y] = heapq.heappop(q)
        if distance[x][y] < dist:
            continue
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<M:
                cost = distance[x][y] + int(graph[nx][ny])
                if cost < distance[nx][ny]:
                    distance[nx][ny] = cost
                    heapq.heappush(q,(cost, [nx,ny]))

dijkstra([0,0])
print(distance[N-1][M-1])