[백준] 1948번 : 임계경로 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1948번: 임계경로

 

1. 문제 설명

2. 풀이과정

해당 문제에서는 출발 도시와 도착 도시가 주어지기 때문에 일반적인 위상 정렬이 아닌 시작점을 출발 도시로 지정하고 위상 정렬을 수행하면서 출발 도시에서 도착 도시까지 거치는 모든 도시와 관련된 임계 경로값을 구할 수 있다.

단, 해당 문제의 핵심은 1분도 쉬지 않고 달려야 하는 도로의 수를 구하는 것인데, 이를 해결하려면 에지 뒤집기라는 아이디어가 필요하다.

(에지 뒤집기 아이디어는 그래프 문제에서 종종 나오는 개념이므로 해당 문제를 이용해 학습해 본다.)

 

인접 리스트에 노드 데이터를 저장하고, 진입 차수 리스트 값을 업데이트한다.

이때 에지의 방향이 반대인 역방향 인접 리스트도 함께 생성하고 저장한다.

시작 도시에서 위상 정렬을 수행해 각 도시와 관련된 임계 경로를 저장한다.

도착 도시에서 역방향으로 위상 정렬을 수행한다.

이때 '이 도시의 임계 경로값 + 도로 시간 == 이전 도시의 임계 경로값'일 경우에는 이 도로를 1분도 쉬지 않고 달려야 하는 도로로 카운팅하고, 이 도시를 큐에 삽입하는 로직으로 구현해야 한다.

도착 도시의 임계 경로값과 1분도 쉬지 않고 달려야 하는 도로의 수를 출력한다.

 

1분도 쉬지 않고 달려야 하는 도로로 이어진 노드와 연결된 다른 도로만이 1분도 쉬지 않고 달려야 하는 도로의 후보가 될 수 있으므로 해당 메커니즘을 바탕으로 노드를 큐에 삽입해야 한다.

또한 중복으로 도로를 카운드 하지 않기 위해 이미 방문한 적이 있는 한 노드는 큐에 넣지 않아야 한다.

 

슈도코드

1. n(도시 수) 입력받기
2. m(도로 수) 입력받기
3. graph(도시 인접 리스트)
4. reverseGraph(역방향 도시 인접 리스트)
5. indegree(진입 차수 리스트)
6. for m만큼 반복:
   1. start, end, time 각각 입력받음
   2. 인접 리스트에 데이터 저장, 도착 도시와 시간을 리스트의 형태로 묶어서 저장 [end, time]
   3. 역방향 인접 리스트에도 데이터 저장, 시작 도시와 시간을 리스트의 형태로 묶어서 저장 [start, time]
   4. 도착 도시에 대한 진입 차수 리스트 저장
7. 시작 도시, 도착 도시 데이터 입력받기
8. 큐 생성
9. 출발 도시를 큐에 삽입
10. result(결과)
11. while (큐가 빌 때까지):
    1. 현재 노드 = 큐에서 데이터 가져오기
    2. for 현재 노드에서 갈 수 있는 노드 탐색:
       1. 다음 노드 진입 차수 리스트 1 감소
       2. result = 다음 노드의 현재 경로값과 현재 노드의 경로값 + 도로 시간 중 큰 값으로 저장
       3. if (다음 노드의 진입 차수 == 0): 큐에 다음 노드 추가
12. roadCount(1분도 쉬지 않고 달려야 하는 도로의 수) 초기화
13. visited(각 도시의 방문 유무 저장할 리스트) 초기화
14. 기존에 사용한 큐 초기화
15. 큐에 도착 도시 삽입
16. visited 리스트에 도착 도시를 방문 도시로 표시
17. while (큐가 빌 때까지):
    1. 현재 노드 = 큐에서 데이터 가져오기
    2. for 역방향 기준으로 현재 노드에서 갈 수 있는 노드 탐색:
       1. if (다음 노드의 result 값 + 도로를 걸리는 데 지나는 시간(에지) == 현재 노드의 result 값):
          1. 1분도 쉬지 않고 달려야 하는 도로 값 1 증가
          2. if (아직 방문하지 않은 도시):
             1. visited 리스트에 방문 도시 표시
             2. 큐에 다음 노드 추가
18. 만나는 시간 result[도착 도시] 출력
19. 1분도 쉬지 않고 달려야 하는 도로의 수 resultCount 출력

반응형

3. 소스코드

import sys
from collections import deque

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

graph = list([] for _ in range(n + 1))
reverseGraph = list([] for _ in range(n + 1))
indegree = [0] * (n + 1)

for _ in range(m):
    start, end, time = map(int, sys.stdin.readline().split())
    graph[start].append([end, time])
    reverseGraph[end].append([start, time])
    indegree[end] += 1

startCity, endCity = map(int, sys.stdin.readline().split())

queue = deque()
queue.append(startCity)

result = [0] * (n + 1)

while (queue):
    now = queue.popleft()
    for next in graph[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])

roadCount = 0
visited = [True] * (n + 1)

queue.clear()
queue.append(endCity)
visited[endCity] = False

while (queue):
    now = queue.popleft()
    for next in reverseGraph[now]:
        if (result[next[0]] + next[1] == result[now]):
            roadCount += 1
            if (visited[next[0]]):
                visited[next[0]] = False
                queue.append(next[0])

print(result[endCity])
print(roadCount)