https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 풀이 다익스트라 알고리즘을 사용했으며 문제에서 목적지까지 최단경로로 이동하는데 주어진 교차로를 무조건 지나야한다. 출발지 - g - h - 목적지 혹은 출발지 - h - g - 목적지가 출발지 - 목적지까지의 최단경로와 동일하다면 교차로를 지나가는것이다. 다만 교차로를 지나가지않는데도 최단경로 값이 같을 수 있지않나 싶다.(입력값이 그렇게 주어진다면..) 다른분들의 풀이를 보니 지나가야하는 ..

https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 풀이 시작값이 주어졌기에 다익스트라 알고리즘으로 풀어주었다. # 10282번 해킹 import sys import heapq input = sys.stdin.readline 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/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/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 풀이 플로이드 워셜 알고리즘을 사용해서 풀어주었다. 블로그 글 참고. https://sunghyun98.tistory.com/66 [알고리즘] 플로이드 워셜 최단경로 알고리즘이며 모든 노드에서 모든 노드로부터 최단경로를 구할 때 사용하는 알고리즘이다. 플로이드 워셜 vs 다익스트라 저번 시간에 다뤘던 한 지점에서 모든 노드로의 최단경로를 sunghyun98.tistory...

https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 풀이 음수간선이 포함되었기에 벨만 포드 알고리즘을 사용한다. 만일 n번의 시도에서도 최단경로간 갱신된다면 음수간선이 존재한다. # 1865번 웜홀 import sys input = sys.stdin.readline INF = int(1e9) def bf(): distance = [INF] * (n+1) # 시작 노드에 대해서 초기화 distance[1] = 0 # 전체 n번의 라운드(..

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/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이 음수의 간선이 포함되었기에 벨만 포드 알고리즘으로 문제를 풀어준다. 벨만포드의 알고리즘은 다익스트라 알고리즘의 최적의 해를 포함한다. 다만 시간복잡도가 다익스트라에 비해 높다.자세한 내용은 https://sunghyun98.tistory.com/51 이 글에서 확인 할 수 있다. # 11657번 타임머신 # 벨만 포드 알고리즘 im..

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번 특정한 ..