Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 에라토스테네스의 체
- 맵
- 애드 혹
- 문자열
- boj
- 슬라이딩 윈도우
- 정렬
- JavaScript
- 싸피
- 수학
- 플로이드-워셜
- 투 포인터
- 브루트포스
- 누적 합
- SSAFY
- 13164
- 해시 테이블
- BFS
- DFS
- 트리
- DP
- 세그먼트 트리
- 모던 JavaScript 튜토리얼
- 구현
- 정수론
- 그래프
- 그리디
- 이분 탐색
- 2357
- Python
Archives
- Today
- Total
흙금이네 블로그
[BOJ] 1948 - 임계경로 (Python) 본문
아이디어
위상 정렬로 각 도시에 도착하는 가장 늦는 시간을 구한 뒤, 도착지로부터 역으로 쉬지 않고 달리는 도로를 찾아 나간다.
풀이
입력 값들의 관계에 따라 출발 도시 리스트 parent와 도착 도시 리스트 child에 도시와 시간을 저장하고,
입력차수 리스트 degree에서 도착 도시 번호의 입력차수 값을 증가시켜 나간 후 함수 find_time과 find_road를 호출한다.
함수 find_time는 BFS로 각 도시에 도착하는 가장 늦는 시간을 구해 리스트 max_time에 저장한다.
가장 늦는 시간을 구하기 위해 방문하려는 도시의 진입차수 degree 값이 0이 되면 큐에 넣고 탐색하도록 한다.
함수 find_road는 BFS로 두 도시의 max_time 값의 차를 구해 해당 도로를 지나는 시간과 같다면 결과값을 증가시킨다.
이때 방문은 한 번만 이뤄지면 되므로 방문 표시 리스트 visited로 방문 여부를 확인하고 큐에 넣어 탐색한다.
도착지로부터 BFS를 해야 임계 경로가 아닌 도로들을 제외해 나가며 해당 도로의 임계 경로 여부를 파악할 수 있다.
import sys
input = sys.stdin.readline
def find_time():
queue = [start]
while queue:
idx = queue.pop(0)
for i, t in child[idx]:
max_time[i] = max(max_time[i], max_time[idx]+t)
degree[i] -= 1
if degree[i] == 0:
queue.append(i)
def find_road():
queue = [end]
visited = [0]*(n+1)
res = 0
while queue:
idx = queue.pop(0)
for i, t in parent[idx]:
if max_time[idx]-max_time[i] == t:
res += 1
if not visited[i]:
queue.append(i)
visited[i] = 1
return res
n = int(input())
m = int(input())
child = [[] for _ in range(n+1)]
parent = [[] for _ in range(n+1)]
degree = [0]*(n+1)
for _ in range(m):
s, e, t = map(int, input().split())
child[s].append((e, t))
parent[e].append((s, t))
degree[e] += 1
start, end = map(int, input().split())
max_time = [0]*(n+1)
find_time()
print(max_time[end])
print(find_road())
가장 늦는 시간을 구할 때 위상 정렬을 하지 않으면 불필요한 재탐색이 반복되어 시간 초과가 발생한다.
도착 도시 방문 이전에 해당 도시로 가는 모든 출발 도시에 대한 방문이 이뤄져야 하므로 위상 정렬이 사용된다.
# 시간 초과 코드
queue = [start]
while queue:
idx = queue.pop(0)
for i, t in child[idx]:
max_time[i] = max(max_time[i], max_time[idx]+t)
queue.append(i)
'알고리즘' 카테고리의 다른 글
[BOJ] 1525 - 퍼즐 (Python) (0) | 2023.01.14 |
---|---|
[BOJ] 1781 - 컵라면 (Python) (1) | 2023.01.14 |
[BOJ] 7453 - 합이 0인 네 정수 (Python) (0) | 2023.01.11 |
[BOJ] 11812 - K진 트리 (Python) (0) | 2023.01.10 |
[BOJ] 17435 - 합성함수와 쿼리 (Python) (0) | 2023.01.09 |
Comments