알고리즘/BOJ
[BOJ 20046, Python 3] Road Reconstruction
70825
2021. 9. 8. 18:31
반응형
https://www.acmicpc.net/problem/20046
20046번: Road Reconstruction
입력은 표준입력을 사용한다. 첫 번째 줄에 도시를 표현하는 격자의 행과 열의 크기를 각각 나타내는 두 개의 양의 정수 m, n (1 ≤ m, n ≤ 1,000, 1 < m×n)이 주어진다. 다음 m개의 각 줄에 격자의 각
www.acmicpc.net
풀이
일단 BFS를 생각해볼 수 있는데 도로의 비용이 0 또는 1뿐이라면 덱을 활용한 0-1 BFS를 생각해볼 수 있지만, 비용이 0, 1, 2로 총 세가지이기 때문에 BFS로는 풀기 힘들 것 같고, 다익스트라 알고리즘을 사용하면 됩니다.
참고로 문제에 (0, 0)의 값이 -1일 수도 있다는 점을 주의해주시면 됩니다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
from heapq import *
input = __import__('sys').stdin.readline
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
MAX = 987654321
m, n = map(int, input().split())
MAP = [[*map(int, input().split())] for _ in range(m)]
S = [[MAX] * n for _ in range(m)]; S[0][0] = MAP[0][0]
q = []; heappush(q, [MAP[0][0], 0, 0]) # 비용, (x, y)
if MAP[0][0] == -1:
print(-1)
exit()
while q:
t, x, y = heappop(q)
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < m and 0 <= ny < n and MAP[nx][ny] != -1 and S[nx][ny] > t + MAP[nx][ny]:
S[nx][ny] = t + MAP[nx][ny]
heappush(q, [S[nx][ny], nx, ny])
print([S[m-1][n-1], -1][S[m-1][n-1] == MAX])
|
cs |
반응형