20046번: Road Reconstruction
입력은 표준입력을 사용한다. 첫 번째 줄에 도시를 표현하는 격자의 행과 열의 크기를 각각 나타내는 두 개의 양의 정수 m, n (1 ≤ m, n ≤ 1,000, 1 < m×n)이 주어진다. 다음 m개의 각 줄에 격자의 각
www.acmicpc.net
아이디어:
차량은 가로나 세로방향으로만 움직이므로 현재 위치에 인접한 정점은 상하좌우 좌표라고 할 수 있다.
그럼 인접한 정점을 이동하면서 최소 비용을 업데이트하면 되지 않을까? 했는데 해결됐다!ㅎㅎ
그냥 다익스트라 알고리즘과 똑같이 구현하면 된다.
import sys, heapq
m, n = map(int, sys.stdin.readline().split())
graph = []
for _ in range(m):
graph.append(list(map(int, sys.stdin.readline().split())))
xx = [1,-1,0,0]
yy = [0,0,1,-1]
INF = 9999999
ans = [[INF]*n for _ in range(m)]
def solve(X, Y):
if (graph[Y][X]==-1):
print(-1)
sys.exit(0)
h = []
ans[Y][X] = graph[Y][X]
heapq.heappush(h, [ans[Y][X],X,Y])
while(h):
now_cost, now_x, now_y = heapq.heappop(h)
if (now_cost>ans[now_y][now_x]): continue
for i in range(4):
x = now_x + xx[i]
y = now_y + yy[i]
if (x>=0 and x<n and y>=0 and y<m):
if(graph[y][x]==-1): continue
cost = now_cost + graph[y][x]
if (cost<ans[y][x]):
ans[y][x] = cost
heapq.heappush(h, [ans[y][x], x, y])
if (ans[m-1][n-1]==INF): print(-1)
else: print(ans[m-1][n-1])
solve(0,0)
'알고리즘💻 > 우선순위큐&다익스트라' 카테고리의 다른 글
BOJ 22116번: 창영이와 퇴근 (0) | 2021.08.17 |
---|---|
BOJ 11279번: 최대 힙 (0) | 2021.02.15 |
BOJ 1916번: 최소비용 구하기 (0) | 2021.02.13 |
BOJ 1753번: 최단경로 (0) | 2021.02.13 |
BOJ 11000번: 강의실 배정 (0) | 2021.02.13 |