PS Featured

[PS] BOJ 1948 / 임계 경로

Minjun Kim

01 Dec 2025 • 5 min read

Thumbnail: Photo by Hans (Unsplash)

문제 링크: https://www.acmicpc.net/problem/1948

주어진 방향 그래프에서의 최장 경로를 찾고, 그 경로를 구성하는 간선의 개수를 세는 문제입니다.

풀이

최장 경로 찾기

보통의 그래프 탐색 문제는 최단 경로를 찾지만, 이번 문제에서는 가중치의 합이 가장 큰 경로를 찾아야 합니다. 이를 최장 경로라고 부르겠습니다.

먼저 입력 데이터로 그래프를 구성해야 합니다. 정점의 개수는 10,000개이나 간선의 개수는 최대 100,000개인 희소 그래프이므로 인접 그래프 형태로 그래프를 저장했습니다.

# 0. 입력 처리하기
input = open(0).readline
N = int(input())
M = int(input())
graph = [[] for _ in range(10001)]

for _ in range(M):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))

start, end = map(int, input().split()) # start는 한걸음, end는 로마

입력 처리

이후 BFS를 통해 최장 경로를 구했습니다. time 배열에 현재 정점까지 도달하기 위해 걸리는 최장 시간을 저장했습니다.

from collections import deque

# 1. 최장 경로 구하기
queue = deque([start])
time = [-1] * 10001
time[start] = 0
max_time = 0

while queue:
    prev = queue.popleft()
    
    for v, w in graph[prev]:
        if time[v] == -1 or time[v] < time[prev] + w: # 항상 최장 거리를 기록한다
            time[v] = time[prev] + w
            if max_time < time[v]:
                max_time = time[v]
            queue.append(v)

최장경로 탐색

경로 역추적하기

앞선 BFS로 각 정점에 도달하기까지 걸린 최장 시간을 기록했습니다. 이 정보를 토대로, 그래프를 거꾸로 탐색하면서 최장 경로에 포함되는 간선을 찾아야 합니다.

그래프를 반대로 탐색하기 위해, 그래프를 입력 받는 과정에서 반대 방향의 간선으로 구성되는 그래프를 함께 저장합니다. 모든 간선을 반대 방향으로 연결했으므로, 새롭게 구성된 그래프는 로마(end)에서 출발해 한걸음(start)로 도달하는 형태가 됩니다.

# 0. 입력 처리하기
...
graph = [[] for _ in range(10001)]
backward = [[] for _ in range(10001)]

for _ in range(M):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
    backward[v].append((u, w)) # 역방향 그래프

역방향 그래프 입력받기

이제, 로마(end)에서 출발해 다시 BFS를 진행합니다. 이때, 앞서 기록한 time배열의 정보를 토대로 최장 경로를 구성하는 정점들만 지나며 탐색을 계속합니다.

time배열에 저장된 정보는 "최장 경로"를 기준으로 해당 정점에 도달할 수 있는 최장 시간값입니다. 따라서, 그래프를 역방향으로 탐색할 때 "이전 정점까지의 시간 + 간선의 가중치 = 현재 정점의 시간" 이 성립할 때 이전 정점은 최장 경로에 포함됩니다.

# 2. 역추적으로 경로에 포함되는 간선의 개수 구하기
queue.append(end)
cnt = 0 # 최장 경로에 포함되는 간선의 개수.

while queue:
    now = queue.popleft()
    for prev, w in backward[now]:
        if time[now] == time[prev] + w:
            cnt += 1
            queue.append(prev)

최장 경로 역추적하기

역추적 시 간선의 중복 방지하기

역추적 과정에서 같은 간선을 여러 번 방문할 수 있습니다. 이를 위해, 각 간선의 방문 여부를 기록하고 새로 간선을 방문할 때마다 검사해 간선의 개수가 중복되는 것을 방지했습니다.

# 2. 역추적으로 경로에 포함되는 간선의 개수 구하기
queue.append(end)
cnt = 0
visited = [[False] * 10001 for _ in range(10001)] # 간선 
while queue:
    now = queue.popleft()
    for prev, w in backward[now]:
        if time[now] == time[prev] + w and not visited[prev][now]:
            cnt += 1
            visited[prev][now] = True
            queue.append(prev)

간선 중복 방지하기

전체 코드

from collections import deque

# 0. 입력 처리하기
input = open(0).readline
N = int(input())
M = int(input())
graph = [[] for _ in range(10001)]
backward = [[] for _ in range(10001)]

for _ in range(M):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
    backward[v].append((u, w))

start, end = map(int, input().split())
queue = deque([start])
time = [-1] * 10001
time[start] = 0

# 1. 최장 경로 구하기
max_time = 0
while queue:
    prev = queue.popleft()
    
    for v, w in graph[prev]:
        if time[v] == -1 or time[v] < time[prev] + w: # 처음 방문하거나 더 긴 시간에 도달한 경우 새로 기록한다. 우리는 최장경로가 필요함.
            time[v] = time[prev] + w
            if max_time < time[v]:
                max_time = time[v]
            queue.append(v)

# 2. 역추적으로 경로에 포함되는 간선의 개수 구하기
queue.append(end)
cnt = 0 # 최장 경로에 포함되는 간선의 개수.
# 같은 간선을 중복으로 방문할 수 있다. 이를 처리해야 함.
visited = [[False] * 10001 for _ in range(10001)]
while queue:
    now = queue.popleft()
    for prev, w in backward[now]:
        if time[now] == time[prev] + w and not visited[prev][now]:
            cnt += 1
            visited[prev][now] = True
            queue.append(prev)

print(f"{max_time}\n{cnt}")

solution.py