[Python] 백준 1948번 - 임계경로

문제

• 백준 1948번

최종 코드

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
m = int(input())
routes = [[] for _ in range(n + 1)]
degree = [0] * (n + 1)
reversed_routes = [[] for _ in range(n + 1)]
max_time = [0] * (n + 1)

for _ in range(m):
    s, e, t = map(int, input().split())
    routes[s].append((e, t))
    degree[e] += 1
    reversed_routes[e].append((s, t))

start, end = map(int, input().split())

que = deque()
que.append(start)
while que:
    now = que.popleft()

    for t in routes[now]:
        node, value = t[0], t[1]
        max_time[node] = max(max_time[node], max_time[now] + value)
        degree[node] -= 1

        if degree[node] == 0:
            que.append(node)

print(max_time[end])

que.clear()
que.append(end)
count = 0
visited = [False] * (n + 1)
visited[end] = True
while que:
    now = que.popleft()

    for t in reversed_routes[now]:
        node, value = t[0], t[1]

        if max_time[now] == max_time[node] + value:
            count += 1

            if not visited[node]:
                visited[node] = True
                que.append(node)

print(count)

풀이 과정

---

• 문제에서 입력으로 주어지는 도로의 경우 단방향에 사이클(cycle)이 없다. 또한 출발 도시로 들어오는 도로와 도착 도시에서 나가는 도로가 0개이다
• 무수히 많은 사람이 지도를 제작하기위해 출발 도시에서 도착 도시까지의 모든 경로를 탐색하고 도착 도시에서 만날때, 가장 마지막에 도착하는 사람이 걸리는 시간을 구해야 하는 문제이다
• 여기까지 문제를 읽고 입력으로 주어진 조건과 구해야하는 답을 봤을때까지는 출발 도시에서 출발해서 도착 도시에 어떻게든 도착하도록 구성되어있으므로, 단순히 위상 정렬을 이용해서 차수 리스트가 0인 도시를 골라 그 때 걸린 시간의 최댓값을 더해나가면 되겠다고 생각했다
• 하지만,  단순히 문제에서 요구하는 출력은 최소한 몇 시간후에 만나는지에 대한 것만 아니라 해당 시간에 만나려면 쉬지 않고 달려야하는 사람이 지나는 도로의 수도 있었다..
• 어떻게 풀어야할지 고민하다(한참 고민한 것 같다 ㅎ..) 백준 1516번 게임 개발 문제를 풀 때처럼 각 도시에서 걸린 시간의 최댓값을 배열에 저장하고 각 도시에서 걸린 시간의 최댓값과, 이어진 도시의 걸린 시간의 최댓값과 해당 경로에서 소요되는 시간의 합이 같으면 해당 경로로 오는 경우 시간을 맞추기 위해 쉬지 않고 달려야한다는 것을 깨달았다
•  즉 아래 그림과 같이 계산하면 된다!

초록색: 도시에 도착하는 시간의 최댓값, 파란색: 경로 이동에 소요되는 시간

• 따라서 추가로 처음 경로에대한 정보를 입력할 때, 위의 연산을 편하게 하기 위해서 reversed_routes 리스트에 원래 경로와 방을 반대로 하여 저장하였다!

초기 코드

<hide/>
import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
m = int(input())
routes = [[] for _ in range(n + 1)]
degree = [0] * (n + 1)
reversed_routes = [[] for _ in range(n + 1)]
max_time = [0] * (n + 1)

for _ in range(m):
    s, e, t = map(int, input().split())
    routes[s].append((e, t))
    degree[e] += 1
    reversed_routes[e].append((s, t))

start, end = map(int, input().split())

que = deque()
que.append(start)
while que:
    now = que.popleft()

    for t in routes[now]:
        node, value = t[0], t[1]
        max_time[node] = max(max_time[node], max_time[now] + value)
        degree[node] -= 1

        if degree[node] == 0:
            que.append(node)

print(max_time[end])

que.clear()
que.append(end)
count = 0
visited = [False] * (n + 1)
visited[end] = True
while que:
    now = que.popleft()

    for t in reversed_routes[now]:
        node, value = t[0], t[1]

        if visited[node]:
            continue

        que.append(node)

        if max_time[now] == max_time[node] + value:
            count += 1
            visited[node] = True

print(count)

 

문제점

• 위의 코드 47~48번째 줄에서 한 번 선택된 노드가 다시 선택되는 것을 막기 위해 노드를 선택했었으면 continue 하도록 했지만, 검증을 하는 부분의 위치가 잘못되어 여러 경로가 있는 경우 한 경로만 확인을 하고 넘어가는 문제가 발생했다...

# 선택 된 여부를 검증하는 부분의 위치가 잘못되어 모든 경로를 검사하지 못함
while que:
    now = que.popleft()

    for t in reversed_routes[now]:
        node, value = t[0], t[1]

        if visited[node]:
            continue

        que.append(node)

        if max_time[now] == max_time[node] + value:
            count += 1
            visited[node] = True
            
# 모든 경로에대해 검사를 할 수 있도록 수정
while que:
    now = que.popleft()

    for t in reversed_routes[now]:
        node, value = t[0], t[1]

        if max_time[now] == max_time[node] + value:
            count += 1

            if not visited[node]:
                visited[node] = True
                que.append(node)

• 단순해 보이는 문제였지만, 뒤집어서 문제를 푼다라는 것을 생각하지 못하면 당황스러울 수 있는 문제였다. 그래도 앞으로 문제를 풀면서 생각할 수있는 방법이 늘어서 좋았다!

• 사용했던 반례

// input
5
7
1 2 1
1 3 3
2 3 2
2 4 1
2 5 3
3 5 1
4 5 1
1 5

// output
4
5

 

 

틀린 부분 또는 궁금한 점은 댓글로 남겨주세요! 항상 환영합니다!