4485번: 녹색 옷 입은 애가 젤다지?
https://www.acmicpc.net/problem/4485
문제 정의
주인공 링크는 현재 도둑루피가 가득한 N*N 크기의 동굴안에 젤 안쪽에 있다. ([0][0]에 위치)
동굴의 반대편으로 가야하는데, 도둑루피를 지나면 도둑루피의 크기만큼 소지금을 잃게된다.
한번에 상하좌우 1칸씩 이동할 수 있다.
이 때 잃는 금액을 최소로 하여 동굴을 이동하려고 한다. 링크가 잃을 수 밖에 없는 최소 금액을 구하면 된다.
접근 방법
‘잃을 수 밖에 없는 최소 금액’ = 동굴의 마지막 [N-1][N-1] 로 가는데 드는 비용을 최소화하는 경로로 가야한다.
따라서 최단경로, 다익스트라로 풀 수 있다.
다익스트라는 노드와 간선의 정보가 있어야 하는데, 이 문제에서는 다음과 같다.
- 노드: 도둑루피의 위치
- 간선: 도둑루피의 크기
한가지 조건이 더 있는데 바로 ‘상하좌우’로만 이동할 수 있다는 것이다.
현재 링크가 있는 위치에서 상하좌우가 그래프의 범위를 벗어나지 않는지도 확인해주어야 한다.
최단경로에 필요한 변수는 간선의 크기가 저장된 graph, 그 위치까지 소요되는 최단거리가 저장된 distance가 있다. 이 문제에서는 다음과 같이 접근했다.
graph: 2차원 배열로, 도둑루피가 들어있는 동굴정보(입력 값 그대로다.)
distance: 2차원 배열로, 입력으로 들어온 동굴정보와 크기가 동일하며 초기값은 모든 원소가 1e9로 설정했다.
문제 해설
- N=0 이면 출력이 끝나므로 while 문안에 조건을 두었다.
- graph 변수에 도둑루피 정보를 넣고, distance 변수를 1e9로 초기화한다.
- 다익스트라 구현을 위해 파이썬의 heapq 라이브러리를 사용한다.
✅ 주의할 점
- 링크는 [0][0]에서 출발하므로 distance[0][0]을 0으로 초기화 할까? → 아니다. 왜냐면 [0][0]에도 도둑루피가 있으므로 [0][0]의 도둑루피 크기도 계산해줘야 한다. 따라서
distance[0][0] = graph[0][0]으로 초기화 해준다.
- 동일하게, queue에 출발 노드에 대한 정보를 삽입할 때 (0.0) 위치에 해당하는 도둑루피의 정보를 넣어준다.
heapq.heappush(q, (graph[0][0], (0,0))
- 마지막으로, 다익스트라 동작을 진행하면 distance변수에 각 위치까지 가는 최소 비용이 저장된다.
- 따라서 링크가 [N-1][N-1] 까지 가는데 필요한 최소 비용은 distance[N-1][N-1] 이다.
풀이
# 도둑루피를 지나면 도둑루피의 크기만큼 소지금을 잃는다.
# 잃는 금액을 최소로 하여 동굴을 이동해야함
# 한번에 상하좌우 1칸씩
# 잃을 수 밖에 없는 최소금액은? -> 동굴을 최단경로로 빠져나와야 함. (도둑루피는 적게)
# 노드: 도둑루피 위치, 간선:도둑루피 크기
import sys
import heapq
input = sys.stdin.readline
case = 0
dx = [0, 0, -1, 1] # 상하좌우
dy = [-1, 1, 0, 0]
while True:
case += 1
N = int(input()) # 동굴의 크기 (N*N)
if N == 0:
break
graph = [] # 도둑루피가 들어있는 동굴 정보
for _ in range(N):
graph.append(list(map(int, input().split())))
INF = 1e9
distance = [[1e9]*N for _ in range(N)] # 도둑루피의 위치까지의 최단경로가 저장.
distance[0][0] = graph[0][0]
q = []
heapq.heappush(q, (graph[0][0], (0, 0))) # (도둑루피 크기, (i, j))
while q:
d, now = heapq.heappop(q) # 크기가 작은 순으로
i, j = now[0], now[1]
if distance[i][j] < d: continue # 최단거리가 더 짧으면 갱신 필요 없으므로 다음 loop으로.
#현재 now에 연결된 노드마다 검사해서 최단경로를 업데이트.
for k in range(4):
dx_i = i+dx[k]
dy_j = j+dy[k]
if (dx_i >= 0 and dx_i < N) and (dy_j >= 0 and dy_j < N):
cost = d + graph[dx_i][dy_j]
if distance[dx_i][dy_j] > cost:
distance[dx_i][dy_j] = cost
heapq.heappush(q, (cost, (dx_i, dy_j)))
result = distance[N-1][N-1]
print('Problem {}: {}'.format(case, result))
정리
- 다익스트라 알고리즘의 시간복잡도는 이다.
- 이 문제의 시간복잡도는 case로 들어오는 N까지 고려했을 때, 인데, N은 최대 125이므로, 로 계산할 수 있다.
- 다익스트라 알고리즘을 알고 있다면 수월하게 풀 수 있는 문제인 것 같다.
- 다익스트라 알고리즘 중 우선순위큐 부분에서 살짝 어려웠는데, 아직 익숙치 않아서 그런 것 같다.
- 더 많은 문제를 풀어서 툭 치면 다익스트라를 구현할 수 있도록 연습해야겠다.
Uploaded by N2T