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

🔈 문제

관악산 기슭에는 보름달을 기다리는 달빛 여우가 한 마리 살고 있다. 달빛 여우가 보름달의 달빛을 받으면 아름다운 구미호로 변신할 수 있다. 하지만 보름달을 기다리는 건 달빛 여우뿐만이 아니다. 달빛을 받아서 멋진 늑대인간이 되고 싶어 하는 달빛 늑대도 한 마리 살고 있다.

관악산에는 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번 부터 시작하여 나머지 노드의 방문 시간을 파악할 수 있었지만, 늑대는 조금 달랐다. 처음에는 두배속도로, 다음은 0.5배속으로 또 다음은 2배속도로 이렇게 속도가 변칙적이였다.

방문 시간을 담은 배열을 1차원으로 두면 이것을 체크할 수 없었기에 2차원 배열을 사용하였다.

즉 n번째 노드에 방문하기 전에 2배속으로 왔는지, 0.5배속으로 왔는지 둘 다 담는 것이다.

이렇게 늑대까지 방문 시간을 파악했다면 끝난 것이다. 

여우와 늑대의 방문 속도를 비교하여 여우가 빨리 온것을 카운트하여 출력한다.

 

 

 

💻 코드

import sys, heapq
input = sys.stdin.readline
 
INF = int(1e9)
 
# 여우 데이크스트라
def dijkstra():
    distance = [INF]*(n+1)
    distance[1] = 0
    hq = []
    heapq.heappush(hq, (0,1))
    while hq:
        dist, now = heapq.heappop(hq)
        if distance[now] < dist:
            continue
        for nex,cost in graph[now]:
            if dist+cost<distance[nex]:
                distance[nex] = dist+cost
                heapq.heappush(hq, (cost+dist, nex))
    return distance[2:]
    
 
# 늑대 데이크스트라
def dij_wolf():
    # 2차원 배열
    distance = [[INF]*(2) for _ in range(n+1)]
    distance[1] = [INF,0] #distance[1][1] = 시작, 0번째 인덱스가 0.5배속, 1번째 인덱스가 2배속
    hq = []
    heapq.heappush(hq, (0,1,1))
    while hq:
        dist, now, run = heapq.heappop(hq)
        if distance[now][run]!=dist:
            continue
 
        for nex, cost in graph[now]:
            if run==1 and distance[nex][0]>dist+(cost//2):
                distance[nex][0] = dist+(cost//2)
                heapq.heappush(hq, ((cost//2)+dist, nex,0))
            elif run==0 and distance[nex][1]>dist+(cost*2):
                distance[nex][1] = dist+(cost*2)
                heapq.heappush(hq, ((cost*2)+dist, nex, 1))
 
 
    return distance[2:]
 
def result(a,b):
    res = 0
    for i in range(n-1):
        if a[i]<min(b[i]):
            res += 1
    return res
 
 
n,m = map(int,input().split())
graph = [[] for _ in range(n+1)]
 
for _ in range(m):
    a,b,d = map(int,input().split())
    d*=2 # 담을때 X2 담음. 왜? 늑대 0.5에서 실수 연산 
    graph[a].append((b,d))
    graph[b].append((a,d))
 
fox = dijkstra()
wolf = dij_wolf() 
 
print(result(fox,wolf))

 

🍭 시행착오

pypy가 시간초과가 발생한 이유는 나도 모르겠닿

🔗 문제링크 달빛 여우

16118번: 달빛 여우