[백준 16118번] 파이썬 - 달빛 여우

백준 16118 - 달빛 여우

시간 제한 1초(추가 시간 x), 메모리 제한 512MB

# 조건

• 관악산 기슭에는 보름달을 기다리는 달빛 여우가 한 마리 살고 있다.
• 달빛 여우가 보름달의 달빛을 받으면 아름다운 구미호로 변신할 수 있다.
• 하지만 보름달을 기다리는 건 달빛 여우뿐만이 아니다.
• 달빛을 받아서 멋진 늑대인간이 되고 싶어 하는 달빛 늑대도 한 마리 살고 있다.
• 관악산에는 1번부터 N번까지의 번호가 붙은 N개의 나무 그루터기가 있고, 그루터기들 사이에는 M개의 오솔길이 나 있다.
• 오솔길은 어떤 방향으로든 지나갈 수 있으며, 어떤 두 그루터기 사이에 두 개 이상의 오솔길이 나 있는 경우는 없다.
• 달빛 여우와 달빛 늑대는 1번 나무 그루터기에서 살고 있다.
• 보름달이 뜨면 나무 그루터기들 중 하나가 달빛을 받아 밝게 빛나게 된다.
• 그러면 달빛 여우와 달빛 늑대는 먼저 달빛을 독차지하기 위해 최대한 빨리 오솔길을 따라서 그 그루터기로 달려가야 한다.
• 이 때 달빛 여우는 늘 일정한 속도로 달려가는 반면, 달빛 늑대는 달빛 여우보다 더 빠르게 달릴 수 있지만 체력이 부족하기 때문에 다른 전략을 사용한다.
  • 달빛 늑대는 출발할 때 오솔길 하나를 달빛 여우의 두 배의 속도로 달려가고, 그 뒤로는 오솔길 하나를 달빛 여우의 절반의 속도로 걸어가며 체력을 회복하고 나서 다음 오솔길을 다시 달빛 여우의 두 배의 속도로 달려가는 것을 반복한다.
• 달빛 여우와 달빛 늑대는 각자 가장 빠르게 달빛이 비치는 그루터기까지 다다를 수 있는 경로로 이동한다.
  • 따라서 둘의 이동 경로가 서로 다를 수도 있다.
• 출제자는 관악산의 모든 동물을 사랑하지만, 이번에는 달빛 여우를 조금 더 사랑해 주기로 했다.
• 그래서 달빛 여우가 달빛 늑대보다 먼저 도착할 수 있는 그루터기에 달빛을 비춰 주려고 한다. 이런 그루터기가 몇 개나 있는지 알아보자.

입력

• 첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다.
• 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b, 1 ≤ d ≤ 100,000)가 주어진다.
• 이는 a번 그루터기와 b번 그루터기 사이에 길이가 d인 오솔길이 나 있음을 의미한다.

출력

• 첫 줄에 달빛 여우가 달빛 늑대보다 먼저 도착할 수 있는 나무 그루터기의 개수를 출력한다.

# 접근 방법

• 1번 노드에서 모든 노드까지의 최단 거리를 구하는 문제이다.
  • 다익스트라를 이용하여 풀 수 있을 것 같다.
• 또한 달빛 늑대는 여우의 1/2 속도 또는 2배의 속도로 가기 때문에 계산하기 편하게 모든 노드의 거리를 * 2를 해준다.
• 다익스트라 함수의 인자로는 달빛 늑대와 달빛 여우 각각의 dist 배열과 현재가 여우인지 늑대인지를 구분할 0 또는 1을 넣어준다.
• 늑대의 dist 배열은 빠르게 출발, 느리게 출발을 나누어 dist[i][j]로 사용해준다.
  • j가 0인 경우 빠르게 도착한 경우
  • j가 1인 경우 느리게 도착한 경우
  • 따라서 시작은 빠르게 출발해야하므로 0번 인덱스의 1번 => 직전에 느리게 도착한 경우만 0으로 초기화해준다.
• 만약 늑대인 경우 heapq에 현재의 카운팅을 넣어서 짝수번째이면 // 2, 홀수 번째이면 * 2를 더해주어야 한다.
• 또한 현재 출발 노드 번호, 지금까지의 거리, 연산 횟수 현재 노드를 heappop을 하여 구한 후
  • dist[node] 보다 지금까지의 거리가 크다면 continue를 해준다.
  • 이 때, 늑대의 경우 지금 빨리 출발해야 한다면 => 느리게 도착한 값과 비교
  • 느리게 출발한다면 => 빠르게 도착한 값과 비교해주어야 한다.
  • 지금 빠르게 가야 한다면 dist에 기록된 값은 느리게 온 값이 기록 되어있기 때문에!

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from heapq import heappop, heappush  

def solve():  
    def djikstra(dist, who):  
        q = []  
        # 가중치, 현재 노드 번호, 연산 횟수  
        heappush(q, [0, 0, 0])  
        while q:  
            val, node, cnt = heappop(q)  
            # 여우의 경우 현재 노드에 기록된 값 바로 비교  
            if not who and val > dist[node]:  
                continue  
            # 늑대의 경우 현재 빨리 출발해야 한다면 이전의 느리게 도착한 결과  
            # 느리게 출발한다면 이전의 빠르게 도착한 결과와 비교해주어야 한다.            
            elif who and val > dist[node][cnt%2-1]:  
                continue  
            for next_node, next_val in graph[node]:  
                if not who:  
                    temp = val + next_val  
                    if dist[next_node] > temp:  
                        dist[next_node] = temp  
                        heappush(q, [temp, next_node, cnt])  
                else:  
                    if cnt % 2:  
                        temp = val + 2*next_val  
                    else:  
                        temp = val + next_val // 2  
                    if dist[next_node][cnt%2] > temp:  
                        dist[next_node][cnt%2] = temp  
                        heappush(q, [temp, next_node, cnt+1])  

    N, M = map(int, input().split())  
    graph = [[] for _ in range(N)]  
    for _ in range(M):  
        a, b, c = map(int, input().split())  
        graph[a-1].append((b-1, c*2))  
        graph[b-1].append((a-1, c*2))  

    # 각각 노드까지의 거리 체크 리스트  
    fox_dist = [0] + [float('inf')] * (N-1)  
    # 늑대의 경우 0번 => 빠르게 도착하는 것, 1번 => 느리게 도착하는 것으로 나누기  
    # 처음 시작은 빠르게 출발하므로 0번 노드의 1번(느리게 도착)만 0으로 초기화    
    wolf_dist = [[float('inf'),0]] + [[float('inf'), float('inf')] for _ in range(N-1)]  
    djikstra(fox_dist, 0)  
    djikstra(wolf_dist, 1)  

    print(sum(1 for i in range(N) if fox_dist[i] < min(wolf_dist[i][0], wolf_dist[i][1])))  
    print(wolf_dist)  
solve()