[Baekjoon] 14942번 : 개미

1. 문제

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

• 다익스트라 문제

// 문제
개미집은 n개의 방으로 구성되어 있으며 
n개의 방은 1번부터 n번 까지 번호가 부여되어 있다. 
그 중에서 1번 방은 지면에 바로 연결되어 있는 방이다. 
각 방들은 서로 굴을 통해 연결되어 있다. 
각 굴을 이동하기 위해서는 굴의 길이만큼 에너지가 소모된다.

개미는 집짓기의 달인이기 때문에 불필요한 굴은 짓지 않는다. 
그래서 굴을 타고 한 방에서 다른 방으로 갈 수 있는 경로는 항상 존재하며 유일하다. 
임의의 두 방 사이의 거리는 두 개의 방을 연결하는 경로를 구성하는 굴의 길이의 합이다.

겨울잠을 자던 개미들은 겨울잠에서 깨어나 지면으로 올라가 햇살을 보고 싶어한다. 
그렇기 때문에 지면과 연결된 1번 방으로 이동을 하려고 한다. 
하지만 불행하게도 개미는 긴 겨울잠을 자느라 축적해 놓은 에너지가 적다. 
그래서 개미는 에너지를 1번 방에 도달하기 전에 모두 소모 할 수도 있다. 
이렇게 에너지가 0이 된 개미는 더 이상 움직일 수 없다. 
또한 1번 방에 도착한 개미는 더 이상 움직이지 않는다.

현재 모든 방에는 개미가 한 마리씩 있고 각각의 개미는 각자 축적된 에너지를 가지고 있다. 
잠에서 깨어난 모든 개미는 1번 방을 향해서 이동한다. 
이때 각각의 개미에 대해 도달할 수 있는 방 중에서 
가장 1번 방에 가까운 방의 번호를 출력하시오.

// 입력
자연수 n이 주어진다. n은 방의 개수이다. (1 ≤ n ≤ 105) 
다음 n개의 줄에는 차례대로 현재 각각의 개미가 보유하고 있는 에너지 값이 주어진다. 
i+1번째 줄에는 i번째 방에 있는 개미가 가진 
에너지를 나타내는 100,000이하의 자연수 값이 주어진다. 
이후 n-1개의 줄에는 두 개의 방을 연결하는 굴의 정보가 3개의 정수 a b c 으로 주어진다. 
a, b는 연결된 방을 의미하고 c는 이 굴의 길이를 의미한다. 
굴의 길이는 10,000 이하의 자연수이다.

// 출력
n개의 줄을 출력한다. 
i번째 줄에는 i번 방에 있던 개미가 도달할 수 있는 방 중에 
1번 방과 가장 가까운 방의 번호를 출력한다.

// 예제 입력 1 
4
10
8
22
18
1 2 10
2 3 10
2 4 10

// 예제 출력 1 
1
2
1
2

2. 핵심 아이디어

• 다익스트라를 도착지점으로부터 실행

3. Python 문제풀이

import sys, heapq
input = sys.stdin.readline
INF = 10000000000000000000000

n = int(input())
ant = []
for i in range(n) :
  temp = int(input())
  ant.append(temp)

adj = [[] for _ in range(n)]
for i in range(n-1) :
  a, b, c = map(int, input().split())
  adj[a-1].append((b-1, c))
  adj[b-1].append((a-1, c))

result = [1]

def dijstra(v) :
  d[v] = 0
  min_q = []
  min_q.append((d[v], v))
  while len(min_q) != 0 :
    distance = min_q[0][0]
    current = min_q[0][1]
    heapq.heappop(min_q)
    if d[current] < distance :
      continue
    for i in range(len(adj[current])) :
      next = adj[current][i][0]
      nextdistance = adj[current][i][1] + distance
      if nextdistance < d[next] :
        d[next] = nextdistance
        path[next].append(current)
        heapq.heappush(min_q, (nextdistance, next))

d = [INF] * n
path = [[] for _ in range(n)]

dijstra(0)
for i in range(1, n) :
  for j in adj[i] :
    if j[0] == path[i][0] :
        path[i].append(j[1])

path[0] = [0,0]

for i in range(1, n) :
  energy = ant[i]
  route = i
  while True :
    energy -= path[route][1]
    if energy < 0 :
      result.append(route + 1)
      break
    elif route == 0 :
      result.append(route + 1)
      break
    route = path[route][0]

for i in result :
    print(i)

4. Java 문제풀이