[백준] 1948 임계경로

문제

• N개의 모든 도시는 M개의 일방통행이고 사이클이 없는 도로를 갖는다.
• 어떤 시작 도시로부터 도착 도시까지 출발해 가능한 모든 경로를 탐색하려고 한다.
• 탐색자들은 탐색 후 도착 도시에서 모두 만나야 한다.
• 탐색자들이 만나는 시간은 출발 도시로부터 최소 몇 시간 후인지 구하고, 1분도 쉬지 않고 달려야 하는 도로의 수가 몇 개인지 구하기
• 출발 도시는 들어오는 도로가 0개이고, 도착 도시는 나가는 도로가 0개다.

 

• 1 <= N <= 10,000
  1 <= M <= 100,000
  
  
  

풀이 1

• 말이 어렵지만 즉, 도착도시까지의 최대 경로(시간)와 최대 경로의 도로의 수를 구하라는 의미다.
• 최대 경로의 도로의 수는, 최대 시간이 10일 때, 10에 해당되는 경로의 모든 도로 수를 의미한다.
• 풀이 자체는 어렵지 않고, 시간초과를 해결하는게 포인트다.

 

DFS -> 시간 초과

import sys
sys.setrecursionlimit(10**4)
input = sys.stdin.readline

def dfs(graph, s, t, r) :
    global time, road
    if not graph[s] :   # 도착도시

        if time == t :
            road = road | r
        elif time < t :
            time, road = t, r
        
    for i in graph[s] :
        r.add((s, i[0]))
        dfs(graph, i[0], t+i[1], r.copy())
        r.remove((s, i[0]))


N = int(input())
M = int(input())
graph = [[]*(N+1) for _ in range(N+1)]
for _ in range(M) :
    a, b, t = map(int, input().split())
    graph[a].append((b, t))
S, E = map(int, input().split())    # 출발도시, 도착도시

time = 0
road = set()
dfs(graph, S, 0, set())
print(time)
print(len(road))

 

풀이 2

• 모든 경로를 탐색하지 않고 최대 경로를 구해야 한다. -> `위상정렬`
• 그리고 최대 시간을 갖는 경로의 도로 개수를 구해야 한다

 

• 1) 최대 시간 구하기
  • 위상정렬을 이용해 진입 차수를 하나씩 줄여가면서 다른 도시로의 이동 시간을 갱신하고,
  • 진입 차수가 0이 되면 다시 해당 도시에서 다른 도시로의 이동을 탐색한다.
  • 이 때, time 리스트에 각 도시로의 최대 이동 시간을 저장하고,
  • A 도시로의 최대 이동 시간에 진입한 각 도시들을 road에 저장한다.
• 2) 도로 개수 구하기
  • 각 도시들은 time에 최대 이동 시간이, road에 해당 이동 시간에 진입한 도시들이 저장되어 있다.
  • 따라서 도착 도시에서부터 역으로 출발 도시까지의 도로들을 모두 구한다. (BFS)

import sys
from collections import deque
sys.setrecursionlimit(10**4)
input = sys.stdin.readline

def dfs(graph, s, t, r) :
    global time, road
    if not graph[s] :   # 도착도시

        if time == t :
            road = road | r
        elif time < t :
            time, road = t, r
        
    for i in graph[s] :
        r.add((s, i[0]))
        dfs(graph, i[0], t+i[1], r.copy())
        r.remove((s, i[0]))


N = int(input())
M = int(input())
graph = [[]*(N+1) for _ in range(N+1)]  
bgraph = [[]*(N+1) for _ in range(N+1)] # 도로 역방향 그래프
in_degree = [0] * (N+1)                 # 차수
time = [0] * (N+1)                      # 해당 도시로의 최대 도착 시간
road = [[] for _ in range(N+1)]         # 해당 도시로의 최대 도착 시간의 진입 도시

for _ in range(M) :
    a, b, t = map(int, input().split())
    graph[a].append((b, t))
    bgraph[b].append(a)
    in_degree[b] += 1
S, E = map(int, input().split())    # 출발도시, 도착도시

# 최대 시간 구하기
q = deque([S])
while q :
    now = q.popleft()   # 현재 도시
    # 현재 도시에서 갈 수 있는 각 도로 탐색
    for i in graph[now] :
        in_degree[i[0]] -= 1
        # 해당 도시로의 이동 시간 갱신
        if time[i[0]] < time[now] + i[1] :
            time[i[0]] = time[now] + i[1]
            road[i[0]] = [now]
        elif time[i[0]] == time[now] + i[1] :
            road[i[0]].append(now)
        
        # 더이상 탐색할 도로가 없는 도시의 경우
        if in_degree[i[0]] == 0 :
            q.append(i[0])

# 도로 개수 구하기
q = deque([E])
route = set()
while q :
    now = q.popleft()
    for nxt in road[now] :
        if (now, nxt) not in route :
            route.add((now, nxt))
            q.append(nxt)

print(time[E])
print(len(route))

 

 

References

• 백준 오늘의 문제