[Python] 백준 1948 임계경로

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

1948번: 임계경로

 

1. 접근 방법

 기본적으로 최단 경로를 찾아야 하는 문제인데, 추가적인 조건이 있어서 접근이 조금 까다로웠다. 시작점부터 도착지까지 최대 시간을 구하는 것은 어렵지 않게 해결할 수 있다. 모든 모로를 확인하며 더 늦은 시간으로 갱신하면 된다. 하지만, '이런 사람들이 지나는 도로의 수를 카운트하여라' 부분에서 시간이 걸렸다.

 문제에서 말한 문장은 수정이 필요해보이지만, 우선 문제 해결과 관련하여 저 말을 더 풀어본다면 다음과 같다. 출발지에서 도착지까지 최대 시간을 구하고, 해당 시간으로 도달할 수 있는 모든 도로의 개수를 세야 한다. 그런데 아래와 같은 예시가 있을 수 있다.

 

 위와 같은 도로에서 1에서 시작하여 5까지 가는 것이 목표이고, 모든 도로 이동에 걸리는 시간이 1로 같다고 할 때, 최단 시간은 3이 되는 것을 알 수 있다. 그리고 3의 시간으로 가는 경로는 2가지이지만, 사용하는 도로의 개수는 1→2→3→5, 1→2→4→5로 6개가 아니라 중복 없이 5개가 돼야 한다. 이 부분을 해결하기 위해 도착지까지 가는 길은 위상 정렬로, 그 도로의 수를 확인하기 위해서는 BFS를 활용했다.

---

2. 풀이 코드

🖥python 코드 링크 : https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/1000/1900/1948.py

GitHub - mintropy/PS: 다양한 알고리즘 문제 풀이 저장소입니다.

📕코드 해설

 두가지 작업을 위하여 크게 2개의 while문으로 구성했고, 각각의 while문을 기준으로 상세하게 살펴보겠다.

 

time = [0] * (N + 1)
parent = [[] for _ in range(N + 1)]
queue = deque([(st, 0)])
while queue:
    x, t = queue.popleft()
    for y, _t in roads[x]:
        in_roads[y] -= 1
        next_time = t + _t
        if time[y] == next_time:
            parent[y].append(x)
        if time[y] < next_time:
            time[y] = next_time
            parent[y] = [x]
        if not in_roads[y]:
            queue.append((y, time[y]))

 첫 번째는 경로를 구하기 위하여 위상 정렬을 활용한다.

time : 최대 시간을 구하는데 활용, 리스트에 시간을 더 느리게 갱신하였고

parent : 나중에 도로의 수를 세기 위하여 각 점의 부모 저장

 

이후 while문에서는 인접 도로를 확인하며 위상 정렬을 적용한다.

 

roads_count = set()
queue = deque([end])
while queue:
    x = queue.popleft()
    for y in parent[x]:
        if (y, x) in roads_count:
            continue
        roads_count.add((y, x))
        if y != st:
            queue.append(y)

 도로의 수를 세는 것은 조금은 번거로울 수 있는 작업이다. 나는 set과 BFS를 활용했다.

while문에서 도착지부터 parent에 저장한 부모를 따라가며 탐색, 인접도로를 set에 저장하는 방식으로 해결했다.

---

3. 생각 정리

 위상 정렬이 아직은 낯설다고 느껴지는 부분도 있고, 위상 정렬 과정에서 생성한 데이터를 또다시 활용하는 형식의 문제를 처음 만나게 되어 문제 해결에 시간이 소모되었다. 위상 정렬을 활용하는 데 있어 쉬운 문제에서는 거의 유사한 방식으로 활용하지만, 조금 난이도가 있는 문제에서의 활용방식이 달라지는 부분을 더 익혀야 될 것 같고, 경로를 역추적하는 경우도 익숙해져야 할 것 같다.