📌 문제 055) 임계 경로 구하기
시간 제한 2초, 플래티넘, 백준 1948번
월드 나라는 모든 도로가 일방통행인 도로이고, 싸이클이 없다. 그런데 어떤 무수히 많은 사람들이 월드 나라의 지도를 그리기 위해서, 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색한다고 한다.
이 지도를 그리는 사람들은 사이가 너무 좋아서 지도를 그리는 일을 다 마치고 도착 도시에서 모두 다 만나기로 하였다. 그렇다고 하였을 때 이들이 만나는 시간은 출발 도시로부터 출발한 후 최소 몇 시간 후에 만날 수 있는가? 즉, 마지막에 도착하는 사람까지 도착을 하는 시간을 의미한다.
어떤 사람은 이 시간에 만나기 위하여 1분도 쉬지 않고 달려야 한다. 이런 사람들이 지나는 도로의 수를 카운트 하여라.
출발 도시는 들어오는 도로가 0개이고, 도착 도시는 나가는 도로가 0개이다.
입력
첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 출발 도시의 번호가 주어지고 그 다음에는 도착 도시의 번호, 그리고 마지막에는 이 도로를 지나는데 걸리는 시간이 주어진다. 도로를 지나가는 시간은 10,000보다 작거나 같은 자연수이다.
그리고 m+3째 줄에는 지도를 그리는 사람들이 출발하는 출발 도시와 도착 도시가 주어진다.
모든 도시는 출발 도시로부터 도달이 가능하고, 모든 도시로부터 도착 도시에 도달이 가능하다.7 # 도시 수 9 # 도로 수 1 2 4 1 3 2 1 4 3 2 6 3 2 7 5 3 5 1 4 6 4 5 6 2 6 7 5 1 7 # 시작 도시, 도착 도시
출력
첫째 줄에는 이들이 만나는 시간을, 둘째 줄에는 1분도 쉬지 않고 달려야 하는 도로의 수가 몇 개인지 출력하여라.
12 5
1단계 문제 분석
- 출발 도시와 도착 도시가 주어지기 때문에 일반적인 위상 정렬이 아닌 시작점을 출발 도시로 지정하고 위상 정렬을 수행하면 출발 도시에서 도착 도시까지 거치는 모든 도시와 관련된 임계 경로 값을 구할 수 있다.
- 단, 이 문제의 핵심은 1분도 쉬지 않고 달려야 하는 도로의 수를 구하는 것인데, 이를 해결하려면 에지 뒤집기라는 아이디어가 필요하다. 에지 뒤집기 아이디어는 그래프 문제에서 종종 나오는 개념이므로 이 문제를 이용해 학습해 보자.
- 인접 리스트에 노드 데이터를 저장하고, 진입 차수 리스트 값을 업데이트한다. 이때, 에지 방향이 반대인 역방향 인접 리스트도 함께 생성하고 저장한다.
- 시작 도시에서 위상 정렬을 수행해 각 도시와 관련된 임계 경로를 저장한다.
- 도착 도시에서 역방향으로 위상 정렬을 수행한다. 이때, '이 도시의 임계 경로 값 + 도로 시간(에지) == 이전 도시의 임계 경로 값'일 경우에는 이 도로를 1분도 쉬지 않고 달려야 하는 도로로 카운팅하고, 이 도시를 큐에 삽입하는 로직으로 구현해야 한다.
- 도착 도시의 임계 경로 값과 1분도 쉬지 않고 달려야 하는 도로의 수를 출력한다.
2단계 슈도 코드
N(도시 수) M(도로 수)
A(도시 인접 리스트) reverseA(역방향 인접 리스트)
indegree(진입 차수 리스트)
for M만큼 반복:
인접 리스트 데이터 저장
역방향 인접 리스트 데이터 저장
진입 차수 리스트 저장
시작 도시, 도착 도시 데이터 받기
# 위상 정렬 수행
큐 생성
출발 도시를 큐에 삽입
result(결괏값)
while 큐가 빌 때까지:
현재 노드 = 큐에서 데이터 가져오기
for 현재 노드에서 갈 수 있는 노드 탐색:
타깃 노드 진입 차수 리스트 1 감소
result = 타깃 노드의 현재 경롯값과 현재 노드의 경롯값 + 도로 시간 값 중 큰 값으로 저장
if 타깃 노드의 진입 차수가 0:
큐에 타깃 노드 추가
resultCount(1분도 쉬지 않고 달려야 하는 도로의 수)
visited(각 도시의 방문 유무 저장)
도착 도시를 큐에 삽입
visited 리스트에 도착 도시를 방문 도시로 표시
# 위상 정렬 역방향 수행
while 큐가 빌 때까지:
현재 노드 = 큐에서 데이터 가져오기
for 현재 노드에서 갈 수 있는 노드의 개수: # 역방향 인접 리스트 기준
if 타깃 노드의 result 값 + 도로를 지나는 데 걸리는 시간(에지) == 현재 노드의 result 값:
1분도 쉬지 않고 달려야 하는 도로 값 1 증가
if 아직 방문하지 않은 도시:
visited 리스트에 방문 도시 표시
큐에 타깃 노드 추가
만나는 시간(result[endDosi]) 출력
1분도 쉬지 않고 달려야 하는 도로의 수(resultCount) 출력3단계 코드 구현
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
M = int(input())
A = [[] for _ in range(N+1)]
reverseA = [[] for _ in range(N+1)]
indegree = [0]*(N+1) # 진입차수 리스트
for i in range(M):
S, E, V = map(int, input().split())
A[S].append((E, V))
reverseA[E].append((S, V)) # 역방향 에지 정보 저장
indegree[E] += 1 # 진입차수 리스트 저장
startDosi, endDosi = map(int, input().split())
queue = deque()
queue.append(startDosi)
result = [0]*(N+1)
while queue: # 위상정렬 수행
now = queue.popleft()
for next in A[now]:
indegree[next[0]] -= 1
result[next[0]] = max(result[next[0]],result[now] + next[1])
if indegree[next[0]] == 0:
queue.append(next[0])
resultCount = 0
visited = [False]*(N+1)
queue.clear()
queue.append(endDosi)
visited[endDosi] = True
while queue: # 위상정렬 reverse 수행
now = queue.popleft()
for next in reverseA[now]:
# 1분도 쉬지 않는 도로 체크
if result[next[0]] + next[1] == result[now]:
resultCount += 1
if not visited[next[0]]:
visited[next[0]] = True
queue.append(next[0])
print(result[endDosi])
print(resultCount)