곰탱이의 공부정리

https://www.acmicpc.net/problem/1238  이 문제는 단방향 엣지가 주어진 그래프에서, 모든 노드에서 특정 노드로  최단거리로 왕복했을 때의 최댓값을 구하는 문제이다.   이 문제는 다익스트라 알고리즘을 사용하면 간편하게 풀 수 있다. 다만 오고 갈 때가 다르기에, 필자는 올때의 그래프, 갈때의 그래프를 따로 만들고 시작점을 X로 하여 모든 노드로 가는 최단거리를 구하고 각 인덱스에서 더해서 최댓값을 구했다. X를 도착으로 하든 시작으로 하든, 어차피 그래프만 거꾸로 뒤집으면 X를 시작으로 하여, 오고가는 것을 다 커버할 수 있다.import sysinput = sys.stdin.readlineimport mathimport heapqdef dijkstra(start,graph)..

https://www.acmicpc.net/problem/1753  이 문제는 간편하게 시작지점에서 다른 모든 지점으로의 최소경로의 길이를 구하는 문제이다.   이 문제는 그냥 데이크스트라 알고리즘을 충실히 구현하면 풀린다. 데이크스트라 알고리즘에 관해서는 https://jangbearbio.tistory.com/102 이 글에서 자세히 다뤘으므로, 이 글에서는 자세히는 다루지 않겠다.  이 문제를 풀면서, 필자는 무의식적으로 데이크스트라 알고리즘을 구현할 때 큐를 말그대로 덱으로 하여, bfs의 큐처럼 사용했지만, 무게를 기준으로 최솟값이 항상 앞으로 튀어나오게 하는 heapq 자료형을 사용하는 것이 시간적이나 알고리즘적으로 더 낫다는 것을 기억하게 되었다. 가장 작은 무게가 먼저 나오기에, 같은 경로..

https://www.acmicpc.net/problem/1916  이 문제는 도시 간의 버스비용이 최소로 해서 출발지와 도착지로 가는 버스비용 중 가장 최소비용을 구하는 문제이다. 이 문제는 정확히 데이크스트라 알고리즘(다익스트라 알고리즘이라고도 불림)을 사용하는 문제이다. 데이크스트라 알고리즘은 거칠게 설명하자면 그래프를 탐색하면서 내가 지나온 비용을 들고 탐색하고, 도시에 도착할 때 마다 그 전의 최소비용과 비교하며 지금이 더 최소라면 새로 업데이트 하는 식으로 한 도시에서 다른 도시로 가는 최소비용을 구하는 알고리즘이다. import sysinput = sys.stdin.readlineimport heapq cities = int(input().rstrip())buses = i..