Dev_Diary

https://www.acmicpc.net/problem/14284기초 다익스트라 문제입니다.간선을 정리해 다익스트라 알고리즘을 통해 최단 거리를 찾아주면 됩니다.import sysimport heapqinput = sys.stdin.readlinedef solution(n, m, edges, s, t): # 그래프 graph = [[] for _ in range(n+1)] for a, b, c in edges: graph[a].append([b, c]) graph[b].append([a, c]) # 최소 가중치 리스트 min_weights = [float('inf') for _ in range(n+1)] # 큐 hq = [[0, s]] ..

https://www.acmicpc.net/problem/1916오랜만에 다익스트라 기초 문제입니다.노드만 잘 정리해서 다익스트라 알고리즘으로 풀면 됩니다.import sysimport heapqinput = sys.stdin.readlinedef solution(N, M, edges, s, e): ## 다익스트라 # 그래프 graph = [[] for _ in range(N+1)] for a, b, c in edges: graph[a].append([b, c]) # 최소 비용 min_cost = [float('inf') for _ in range(N+1)] min_cost[s] = 0 # 큐 q = [[0, s]] # 순회 ..

https://www.acmicpc.net/problem/1719플로이드-워셜 알고리즘으로도 풀 수 있지만 저는 개인적으로 다익스트라를 좋아하기 때문에 다익스트라로 풀었습니다.일반적인 다익스트라로 하나하나 풀며 최단경로를 구한다면 O(ElogV) 의 복잡도를 갖습니다.또 각 노드마다 순회하므로 V_P_2 의 경우의 수를 곱할 수 있습니다.최악의 경우 E = 10000, V = 200 이므로 10000 * log(200) * 200 * 199 의 시간이 걸리게 되므로 대충 정수만 계산해도 제한시간 2 초는 말도 안됨을 알 수 있습니다.즉 다른 방법을 생각해야 합니다. 다익스트라 알고리즘이 작동할 때 기본적인 목표는 A-C 의 최적화된 경로를 찾는 것 이지만 중간에 있는 B 를 거치게 될 경우 A-B / B..

https://www.acmicpc.net/problem/22870 22870번: 산책 (large) 코로나로 인하여 확찐자가 되버려 오늘부터 산책을 하려고 한다. 이를 위해 산책할 경로를 정하려고 한다. 현재 있는 곳 $S$에서 출발하여 $S$와 다른 곳인 $E$를 찍고 다시 $S$로 돌아오는 경로로 www.acmicpc.net 기본적으로 다익스트라를 두 번 사용해주면 풀 수 있는 문제입니다. 다만 최단 거리로 이동할 때 노드 번호가 가장 작은 노드로 이동하는 점이 해결해야 할 가장 큰 포인트라고 할 수 있습니다. A -> B 최단거리를 기록하고 B 노드에서 다시 거슬러 올라가며 최단거리를 탐색할 때 1. 노드 번호가 작은 노드로 거슬러 올라가며 탐색한다. 의 경우에는 최단거리가 1 2 3 4 5 6 ..

https://www.acmicpc.net/problem/14285 14285번: 간선 끊어가기 정점 n개, m개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 그래프 내에 있는 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 제 www.acmicpc.net 설명은 복잡하지만 결국 어떤 경로를 제외한 모든 간선을 제거하고, 남은 경로에서 한 간선을 제거한 뒤, 남은 간선들의 가중치의 합을 총 가중치 합에서 빼주면 되는 문제입니다. 물론 그 값이 최댓값이 되어야 한다는 것이 문제지만 생각을 조금 달리 해보면 쉽게 풀 수 있습니다. 총 가중치 합 - 특정 간선의 가중치 합 을 최대로 만들어야 하는 문제인데, 총 가중치 합은 정해져 있으므로 특정 간선의 ..

https://www.acmicpc.net/problem/5551 5551번: 쇼핑몰 첫째 줄에 도시의 수 N, 도로의 수 M, 쇼핑몰이 있는 도시의 수 K가 주어진다. 도시는 1번부터 N번까지 번호가 매겨져 있다. (2 ≤ N ≤ 3000, 1 ≤ M ≤ 105, 1 ≤ K ≤ N) 다음 M개 줄에는 도로의 정보 a, b, www.acmicpc.net 최단거리 목록을 초기화하지 않고 다른 노드에서 시작하는 다익스트라를 돌리면 어떻게 되는지 생각해보자. 다익스트라 알고리즘은 기본적으로 시작 노드에서 다른 노드들 까지의 최단거리를 구하는 알고리즘이므로 여러 시작노드에서 알고리즘을 돌리면 어느 노드에서 시작했는지는 모르겠지만 하여튼 해당 노드까지 도달하는 최단 거리를 기록하게 된다. 또, a->b / b->..

https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 다익스트라로 최단 경로를 구한 뒤 최단 경로를 모두 제외시키고 다시 다익스트라로 최단경로를 구하면 풀 수 있습니다. 다만 최단경로 중복을 염두에 두고 현재 가중치가 최단 가중치보다 같거나 작을 때 우선순위큐에 넣는 방식으로 풀면 시간이 초과되므로 같을 때와 작을 때로 나누어 알고리즘을 실행해야합니다. #include #include #include #include #..

https://www.acmicpc.net/problem/2325 2325번: 개코전쟁 “앙두레 강”이 개미와 코끼리 결혼식에서 기차를 아름답게 만드는 것을 실패했기 때문에 식장이 아수라장이 되고 결혼이 물거품이 되어버렸다. 급기야는 왕국 간에 분쟁으로 이어져 개미왕 www.acmicpc.net 다익스트라를 여러 번 써주면 풀 수 있는 문제입니다. 우선 어느 경로도 제외하지 않은 상태로 다익스트라를 사용해 최단 경로를 구합니다. 구해진 최단 경로에 포함된 도로들을 하나씩 제외시켜주며 다익스트라를 통해 최단경로의 최댓값을 갱신시켜주면 됩니다. 여기서 최단 경로가 여러 개 나올 수 있다고 생각하고 최단경로를 모두 저장하는 경우가 있습니다. 하지만 모든 최단 경로를 구할 필요는 없습니다. 문제의 1번 예시를 ..

https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 다익스트라와 DP 를 함께 사용해 푸는 문제였습니다. 포장 횟수, pave 를 행으로 도시번호를 열로 최단거리 어레이를 만든 뒤 pave 에 따른 최단거리를 기록해가며 풀어주면 됩니다. pave 가 다를 경우에는 포장의 선후관계가 다음 최단거리에 영향을 끼치지만, pave 가 같은 최단거리에서는 먼저 포장을 했던 지금 포장을 했던 선후 관계가 다음 최단거리에 영..

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net https://dev-diary-0717.tistory.com/114 백준 1967 Python https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 dev-diary-0717.t..