[백준] 1261 알고스팟 (파이썬 python)

 

 

문제 링크

 

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

1261번: 알고스팟

 

 

문제 풀이

 

import heapq

def dijkstra(i, j):
    global result
    q = []
    heapq.heappush(q, (0, i, j))
    visited[i][j] = 1
    distance[i][j] = 0
    while q:
        cnt, x, y = heapq.heappop(q)
        if x == n - 1 and y == m - 1:
            result = min(cnt, result)
        if distance[x][y] < cnt: continue
        for dir in range(4):
            nx, ny = x + dx[dir], y + dy[dir]
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                cnt_break = cnt + int(graph[nx][ny])
                if cnt_break < distance[nx][ny]:
                    distance[nx][ny] = cnt_break
                    heapq.heappush(q, (cnt_break, nx, ny))

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
m, n = map(int, input().split())
graph = [list(input()) for _ in range(n)]
distance = [[1e9] * m for _ in range(n)]
visited = [[0] * m for _ in range(n)]
result = n * m
dijkstra(0, 0)
print(result)

 

 

다익스트라 개념과 BFS 개념을 같이 활용해서 풀이했습니다.

다익스트라는 현재 노드의 비용 + 1이 다음 노드의 비용보다 작다면 그 값으로 갱신하는 알고리즘입니다.

이 알고리즘을 너비우선탐색에 활용하려면 현재 좌표(현재 노드) +1(다음 노드가 벽일 경우) 을 한 값이

상하좌우 네 방향에 위치한 좌표의 값보다 작을 경우 갱신하면 됩니다.