https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 풀이(BFS 풀이) 기존의 BFS문제와 같이 BFS로 주어진 동굴을 탐색할 것입니다. 파이썬에서는 BFS를 사용할 경우 deque를 이용해줍니다.이 deque에 다음 좌표를 집어넣는 조건을 다음과 같이 설정하였습니다. 기존의 저장된 루피 값보다 현재의 루피 값이 작을 경우에만 deque에 좌표를 넣어주었습니다. 모든 좌표가 최소 루피 값을 가질 경우에 BFS함수가 종료됩니다. #..

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 풀이 다익스트라 알고리즘을 사용해서 풀어주면된다. 추가로 경로를 나타내어야하는데 최단경로가 갱신될 때마다 move리스트에 다음노드의 인덱스에 현재 노드를 저장해주었다. 그런 뒤 리스트에 새로 담아주면된다. # 11779번 최소비용 구하기 2 import sys import heapq INF = sys.maxsize input = sys.stdin.readline #..

https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 다익스트라 알고리즘 사용 # 18352번 특정 거리의 도시 찾기 import sys import heapq INF = sys.maxsize def dijkstra(start): q = [] heapq.heappush(q, (0, start)) distance[start] = 0 while q: dist, now = he..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 풀이 1, 단방향문제 최대값이 문제없어서 INF는 10억을 잡아주었다. 2, 각 경우의 수의 distance를 받아서 마을 ->파티 경로랑 파티 -> 마을 경로를 더해서 비교해준다. 마무리만 잘해주면 된다. # 1238번 파티 import sys import heapq input = sys.stdin.readline INF = int(1e9) def dijkstra(..

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 풀이 1, 양방향이고 최대치를 sys.maxsize로 잡아서 문제의 제한사항으로부터 자유로워 졌다. 2, 똑같은 다익스트라문제이지만 무조건 마지막에 주어진 두 정점을 지나야하기때문에 시작값이 매개변수로 주어진 다익스트라 함수를 만들어서 경로 1 - num1 - num2 - n 이랑 1 - num2 - num1 - n을 비교해준다. # 1504번 특정한 ..

https://www.acmicpc.net/problem/14284 14284번: 간선 이어가기 2 정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. www.acmicpc.net 풀이 1, 양방향이며 최대치는 5억이기에 INF는 10억으로 잡아주었다. 2, 다익스트라 적용 # 14284번 간선 이어가기 2 import heapq import sys input = sys.stdin.readline INF = int(1e9) def dijkstra(start, target): q = [] # heapq.heappush(dist, node) heapq.heappush(q,..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 풀이 1, 양방향 문제이다. INF는 10억이기에 int(1e9)로 해주었다. 2, 다익스트라 적용 # 1916번 최소비용 구하기 import heapq import sys input = sys.stdin.readline INF = int(1e9) def dijkstra(start, target): q = [] # heapq.heappush(dist, node) ..

https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 풀이 1, 단방향인것을 주의해서 문제를 풀어주길 바란다. 최대치 또한 고려해서 INF를 sys.maxsize로 고쳐주었다. 2, 다익스트라 적용 # 5972번 택배 배송 import sys import heapq input = sys.stdin.readline INF = sys.maxsize def dijkstra(target): q = [] heapq.heappush(q, (0, 1)) distance[..