[ BOJ / Python ] 20046번 Road Reconstruction
이번 문제는 다익스트라 알고리즘으로 풀 수 있는 문제이다. 우선 그래프를 인접 행렬 형태로 저장하고, 4가지 방향에 대한 탐색을 통하여 그때 그때의 최솟값으로 갱신하는 방식으로 최단거리를 구하였다. 우선 해당 좌표가 -1일 경우에는 접근할 수 없으므로 다음으로 탐색할 수 있는 조건으로 좌표의 값이 -1이 아니고 0<=y<m, 0<=x<m의 범위 안에 있을 경우를 넣어주었다.
- m, n을 입력받는다.
- 그래프로 사용할 리스트 graph를 선언한다.
- m번 반복하는 for문을 돌린다.
-> graph를 입력받는다. graph[0][0]
이 -1일 경우, -1을 출력하고 프로그램을 종료시킨다.- 4가지 방향에 대한 정보를 dy, dx에 짝지어 저장한다.
- 최대값을 저장할 변수 INF에
sys.maxsize
를 저장한다. - 거리를 저장할 리스트 dist를 INF m*n으로 채운다.
dist[0][0]
을graph[0][0]
으로 갱신한다.- 다익스트라에 사용할 큐 q를 최소힙으로 선언하고
(graph[0][0], 0, 0)
을 넣는다. - q가 존재하는 동안 반복하는 while문을 돌린다.
-> q에서 cost, y, x를 추출한다.
-> 만약 cost가dist[y][x]
보다 클 경우, 다음 반복으로 넘어간다.
-> 4번 반복하는 i에 대한 for문을 돌린다.
--> ny를y+dy[i]
로 저장한다.
--> nx를x+dx[i]
로 저장한다.
--> 만약 ny가 0보다 크거나 같고 m보다 작고, nx가 0보다 크거나 같고 n보다 작고,graph[ny][nx]
가 -1이 아닐 경우,
---> nxt_cost를cost+graph[ny][nx]
로 저장한다.
---> 만약 nxt_cost가dist[ny][nx]
보다 작을 경우,
---->dist[ny][nx]
를 nxt_cost로 갱신한다.
----> q에(nxt_cost, ny, nx)
를 넣는다. - 만약
dist[m-1][n-1]
이 INF와 같을 경우, -1을 출력한다. - 그 외에는
dist[m-1][n-1]
을 출력한다.
Code
import sys
import heapq
m, n=map(int, input().split())
graph=[]
for _ in range(m):
graph.append(list(map(int, input().split())))
if graph[0][0]==-1:
print(-1)
quit()
dy=[0, 0, -1, 1]
dx=[-1, 1, 0, 0]
INF=sys.maxsize
dist=[[INF]*n for _ in range(m)]
dist[0][0]=graph[0][0]
q=[]
heapq.heappush(q, (graph[0][0], 0, 0))
while q:
cost, y, x=heapq.heappop(q)
if cost>dist[y][x]:
continue
for i in range(4):
ny=y+dy[i]
nx=x+dx[i]
if 0<=ny<m and 0<=nx<n and graph[ny][nx]!=-1:
nxt_cost=cost+graph[ny][nx]
if nxt_cost<dist[ny][nx]:
dist[ny][nx]=nxt_cost
heapq.heappush(q, (nxt_cost, ny, nx))
if dist[m-1][n-1]==INF:
print(-1)
else:
print(dist[m-1][n-1])
import sys
import heapq
m, n=map(int, input().split())
graph=[]
for _ in range(m):
graph.append(list(map(int, input().split())))
if graph[0][0]==-1:
print(-1)
quit()
dy=[0, 0, -1, 1]
dx=[-1, 1, 0, 0]
INF=sys.maxsize
dist=[[INF]*n for _ in range(m)]
dist[0][0]=graph[0][0]
q=[]
heapq.heappush(q, (graph[0][0], 0, 0))
while q:
cost, y, x=heapq.heappop(q)
if cost>dist[y][x]:
continue
for i in range(4):
ny=y+dy[i]
nx=x+dx[i]
if 0<=ny<m and 0<=nx<n and graph[ny][nx]!=-1:
nxt_cost=cost+graph[ny][nx]
if nxt_cost<dist[ny][nx]:
dist[ny][nx]=nxt_cost
heapq.heappush(q, (nxt_cost, ny, nx))
if dist[m-1][n-1]==INF:
print(-1)
else:
print(dist[m-1][n-1])
Author And Source
이 문제에 관하여([ BOJ / Python ] 20046번 Road Reconstruction), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@xx0hn/BOJ-Python-20046번-Road-Reconstruction저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)