728x90 벨만포드3 [파이썬] 1219 오민식의 고민 (백준) 1. 문제 설명 문제 : 1219 - 오민식의 고민 https://www.acmicpc.net/problem/1219 사용 언어 : 파이썬 (Pypy3) 문제요약 : 각 거리마다 잃는 돈과 얻는 돈이 주어질 때, 최대로 갖게 될 수 있는 돈을 구하라. 이때, 도착을 못하는 경우나 돈을 무한히 많이 가질 수 있는 경우라면 각각 gg와 Gee를 출력하라. (이 문제를 풀면서 오민식보다 더 심한 고민에 빠졌었다.) 2. 문제 풀이 해설 : 일반적인 벨만포드를 사용한다. 이때, 사이클이 존재하는지를 알기 위해 bfs를 사용하였다. 또한 얻을 수 있는 돈과 잃어야 하는 돈이 각각 주어짐으로 해당 구간에서 얻을 수 있는 돈을 미리 구해두었다. 코드 : import sys; input = sys.stdin.readl.. 2023. 12. 31. [파이썬] 1738 골목길 (백준) 1. 문제 설명 문제 : 1738 - 골목길 https://www.acmicpc.net/problem/1738 사용 언어 : 파이썬 (Pypy3) 문제요약 : 각 거리마다 얻거나, 빼앗길 수 있는 금품의 양이 주어졌을 때, 최대의 금품을 갖게 될 수 있는 경로를 구하여라. 알고리즘 : 벨만-포드 2. 문제 풀이 해설 : 일반적인 벨만포드를 이용하여 구할 수 있다. 이때 고려해야 할 점이 몇 가지 있다. 1. 최소 가중치를 찾는 벨만포드와는 다르게, 최대 가중치를 구해야 하므로 distance를 -inf로 초기화해야 한다. (이에 따라 조건식을 조금 바꾸어야 한다.) 2. 중요한 경로 구하기!! 각 노드마다 그 전의 노드를 구해놓아 마지막에 최단 경로를 구한다. 코드 : import sys; input =.. 2023. 12. 31. [파이썬] 1865 웜홀 (백준) 1. 문제 설명 문제 : 1865 - 웜홀 https://www.acmicpc.net/problem/1865 (골3) 사용 언어 : 파이썬 (Pypy3) 사용 알고리즘 : 벨만-포드 알고리즘 문제요약 : M개의 양방향 간선인 도로와 W개의 단방향 간선인 웜홀이 이들을 지나는 시간과 함께 주어졌을 때, 음의 사이클이 있는지 구하여라. 2. 문제 풀이 해설 : 음의 사이클을 찾을 수 있는 벨만포드 알고리즘을 이용한다. 여기서 주의해야 할 점이 있는데, 일반 벨만포드 코드와 다르게 아래 코드를 삭제해야 한다. distance[now_node] != INF 왜냐하면 위 코드는 'start'라는 지점에서부터 연결된 각 노드까지의 최단 경로를 구하는 코드이다. 하지만 이 문제에서는 시작 지점이 주어지지 않고, 음의.. 2023. 12. 28. 이전 1 다음 728x90
