미소를뿌리는감자의 코딩
[백준 2024/09/25] 1948번 임계경로 본문
728x90
1. 문제
https://www.acmicpc.net/problem/1948
2. 접근 방법
최대 cost 를 0으로 채워두고, 해당 노드까지 방문할 cost 중 제일 높은 cost로 수정해주는 방식으로 적용하였다.
따라서 while dq 문을 수행하고 나면, cost 별 idx에 가장 높은 cost가 저장되어 있게 된다.
뒤에서 부터 앞으로 진행하며, (reverse_edges) 이용.
cost[u] == cost[v] + w 를 통해서 거리의 합이 최대가 될 수 있는 경로를 탐색하도록 구상한다.
해당 과정에서, stack 에 해당 노드를 넣었는지 유무를 파악하기 위해 visited 함수를 이용해 준다.
3. 코드
from collections import deque
def longest(start, end):
cost = [0] * (n+1)
reverse_edges = [[] for i in range(n+1)]
dq = deque()
dq.append(start)
while dq:
u = dq.popleft()
for v, w in edges[u]:
if cost[v] < cost[u] + w:
cost[v] = cost[u] + w
ind[v] -= 1
reverse_edges[v].append([u, w])
if ind[v] == 0:
dq.append(v)
stack = []
visited = [False] * (n+1)
stack.append(end)
critical_cnt = 0
while stack:
u = stack.pop()
for v, w in reverse_edges[u]:
if cost[u] == cost[v] + w:
critical_cnt += 1
if not visited[v]:
visited[v] = True
stack.append(v)
print(cost[end])
print(critical_cnt)
if __name__ == "__main__":
n = int(input())
m = int(input())
edges = [[] for i in range(n+1)]
ind = [0] * (n+1)
for _ in range(m):
u, v, w = map(int, input().split())
edges[u].append([v, w])
ind[v] += 1
start, end = map(int, input().split())
longest(start, end)
728x90
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/09/28] 9251번 LCS (0) | 2024.09.28 |
---|---|
[백준 2024/09/28] 1904번 01타일 (1) | 2024.09.28 |
[백준 2024/09/24] 2637번 장난감 조립 (0) | 2024.09.24 |
[백준 2024/09/23] 2252번 줄 세우기 (0) | 2024.09.23 |
[백준 2024/09/23] 2294번 동전 2 (0) | 2024.09.23 |