[백준 1948] 임계경로 - 위상 정렬, 역추적

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

1948번: 임계경로

문제

월드 나라는 모든 도로가 일방통행인 도로이고, 싸이클이 없다. 그런데 어떤 무수히 많은 사람들이 월드 나라의 지도를 그리기 위해서, 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색한다고 한다.

이 지도를 그리는 사람들은 사이가 너무 좋아서 지도를 그리는 일을 다 마치고 도착 도시에서 모두 다 만나기로 하였다. 그렇다고 하였을 때 이들이 만나는 시간은 출발 도시로부터 출발한 후 최소 몇 시간 후에 만날 수 있는가? 즉, 마지막에 도착하는 사람까지 도착을 하는 시간을 의미한다.

어떤 사람은 이 시간에 만나기 위하여 1분도 쉬지 않고 달려야 한다. 이런 사람들이 지나는 도로의 수를 카운트하여라.

출발 도시는 들어오는 도로가 0개이고, 도착 도시는 나가는 도로가 0개이다.

입력

첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 출발 도시의 번호가 주어지고 그다음에는 도착 도시의 번호, 그리고 마지막에는 이 도로를 지나는 데 걸리는 시간이 주어진다. 도로를 지나가는 시간은 10,000보다 작거나 같은 자연수이다.

그리고 m+3째 줄에는 지도를 그리는 사람들이 출발하는 출발 도시와 도착 도시가 주어진다.

모든 도시는 출발 도시로부터 도달이 가능하고, 모든 도시로부터 도착 도시에 도달이 가능하다.

출력

첫째 줄에는 이들이 만나는 시간을, 둘째 줄에는 1분도 쉬지 않고 달려야 하는 도로의 수가 몇 개인지 출력하여라.

 

 

 

---

 이 문제는 시작점에서 도착점까지의 시간이 가장 오래 걸리는 경로의 시간과 그러한 시간이 걸리는 경로들의 도로들의 개수를 출력해야 한다.

가장 오래 걸리는 시간은 쉽게 알 수 있으나, 그 도착점에 오기까지 어떤 도로들을 거쳐왔는지를 알아내는 것이 어렵다. 

이동한 도로들을 알기 위해 경로를 역추적하는 방법을 사용했다!

 

 

나는 다익스트라 알고리즘과 위상 정렬 두 가지 방법으로 문제를 풀어보았다.

 

 

 다익스트라 풀이

1. 간선의 정보를 입력받을 때 출발 정점에서 도착 정점까지의 거리 정보뿐만 아니라, 이후의 역추적 과정을 위해 도착 정점에서 출발 정점까지의 거리 정보도 저장해준다.
2. 다익스트라 알고리즘을 통해 출발 정점에서 시작하여 다른 정점까지의 최대 거리들을 저장한다.
3. 도착 정점에서부터 출발하여 지나온 경로들을 역추적한다.
4. "지난 최대 경로 길이 + 도로 길이 == 현재의 최대 경로 길이"이라면 정답 경로의 도로에 포함되므로 개수를 세고, 정점을 방문한 적이 없다면 방문한 후 큐에 새롭게 넣어준다.
5. 시간이 가장 오래 걸리는 경로에서의 시간과 지나온 도로들의 수를 출력한다. 

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

n = int(input())
m = int(input())
edges = [[] for _ in range(n+1)]
edges_rev = [[] for _ in range(n+1)]
for _ in range(m):
    s, e, t = map(int, input().split())
    edges[s].append([e, t])
    edges_rev[e].append([s, t])

s, d = map(int, input().split())


def dijkstra():
    distance = [0 for _ in range(n+1)]
    q = deque([[0, s]])
    while q:
        dist, cur = q.popleft()
        if distance[cur] > dist:
            continue
        for v, w in edges[cur]:
            if dist + w > distance[v]:
                distance[v] = dist + w
                q.append([distance[v], v])
    return distance


def bfs():
    cnt = 0
    visited = [0 for _ in range(n+1)]
    q = deque([e])
    visited[e] = 1
    while q:
        cur = q.popleft()
        for pre_v, pre_c in edges_rev[cur]:
            if distance[pre_v] + pre_c == distance[cur]:
                cnt += 1
                if not visited[pre_v]:
                    q.append(pre_v)
                    visited[pre_v] = 1
    return cnt


distance = dijkstra()
print(distance[d])
print(bfs())

 

 

 위상 정렬 풀이

1. 간선의 정보를 입력받을 때 출발 정점에서 도착 정점까지의 거리 정보뿐만 아니라, 이후의 역추적 과정을 위해 도착 정점에서 출발 정점까지의 거리 정보도 저장해준다.
2. 입력 차수가 0 인 정점들을 큐에 담는다.
3. 큐에서 정점을 하나씩 빼내어 연결되는 간선 정보들을 확인한다. 거리 정보가 최대가 되도록 계속해서 갱신해주고, 간선을 삭제한 후의 입력 차수가 0이 되는 정점들을 큐에 담는다.
4. 도착 정점에서부터 출발하여 지나온 경로들을 역추적한다.
5. "지난 최대 경로 길이 + 도로 길이 == 현재의 최대 경로 길이"이라면 정답 경로의 도로에 포함되므로 개수를 세고, 정점을 방문한 적이 없다면 방문한 후 큐에 새롭게 넣어준다.
6. 시간이 가장 오래 걸리는 경로에서의 시간과 지나온 도로들의 수를 출력한다. 

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

n = int(input())
m = int(input())
inDegree = [0 for _ in range(n+1)]
edges = [[] for _ in range(n+1)]
edges_rev = [[] for _ in range(n+1)]
for _ in range(m):
    s, e, t = map(int, input().split())
    edges[s].append([e, t])
    edges_rev[e].append([s, t])
    inDegree[e] += 1

s, d = map(int, input().split())

q = deque()
for i in range(1, n+1):
    if inDegree[i] == 0:
        q.append(i)

dist = [0 for _ in range(n+1)]
while q:
    cur = q.popleft()
    for v, w in edges[cur]:
        if dist[cur] + w > dist[v]:
            dist[v] = dist[cur] + w
        inDegree[v] -= 1
        if inDegree[v] == 0:
            q.append(v)

cnt = 0
visited = [0 for _ in range(n+1)]
q = deque([d])
while q:
    cur = q.popleft()
    for v, w in edges_rev[cur]:
        if dist[v] + w == dist[cur]:
            cnt += 1
            if not visited[v]:
                visited[v] = 1
                q.append(v)

print(dist[d])
print(cnt)

 

 

위상 정렬을 이용해서도 다익스트라처럼 최대/최소 경로의 길이를 구할 수 있다는 것을 처음 알게 된 문제이다..!