Dev_Diary

https://www.acmicpc.net/problem/5972단순한 다익스트라 문제입니다.준 먹이의 양을 기준으로 알고리즘을 실행하면 됩니다.import sysimport heapq as hqfrom collections import dequeinput = sys.stdin.readlinedef solution(N, M, edges): # 그래프 graph = [[] for _ in range(N+1)] for a, b, c in edges: graph[a].append([b, c]) graph[b].append([a, c]) # 최단여물 min_feeds = [float('inf') for _ in range(N+1)] min_feeds[1]..

https://www.acmicpc.net/problem/13913다익스트라 알고리즘으로 풀 수 있는 문제입니다.각 위치에서 이동할수 있는 범위와 조건에 따라 +1 / -1 / x2 중 선택해 큐에 넣어주며 최단거리를 찾아주면 풀 수 있습니다. 또한 최단시간을 구하며 경로도 기록해주어야 순회를 끝낸 후 역추적을 통해 이동 경로를 찾아낼 수 있습니다.import sysimport heapq as hqfrom collections import dequeinput = sys.stdin.readlinedef solution(N, K): # 최대 인덱스 max_idx = 150000 # 최소 도달 시간 min_times = [float('inf') for _ in range(max_idx+1..

https://www.acmicpc.net/problem/20168다익스트라 알고리즘 문제입니다.보통 탐색할 때 이동 거리를 기준으로 알고리즘을 진행하는데 해당 문제는 지금까지 지나온 최대 코스트를 기준으로 알고리즘을 진행하면 쉽게 풀 수 있습니다.import sysimport heapq as hqinput = sys.stdin.readlinedef solution(N, M, A, B, C, edges): # 그래프 정리 graph = [[] for _ in range(N+1)] for a, b, c in edges: graph[a].append([b, c]) graph[b].append([a, c]) # 큐 q = [[0, A, 0]] #..

https://www.acmicpc.net/problem/17940다익스트라 알고리즘 문제입니다.우선순위 큐를 사용할 때 환승 횟수를 기준으로 정렬하고 알고리즘에서 이동 노드를 가지치기 할 때 환승 횟수와 이동 거리를 모두 사용해줄 수 있습니다. 다만 정렬 기준으로 환승 횟수 / 이동 거리를 모두 사용하면 조금 더 최적화 할 수 있겠지만 현재 알고리즘에서는 이동 거리만 사용해 추후 개선의 여지가 있습니다.import sysfrom heapq import heappop as hppfrom heapq import heappush as hpsinput = sys.stdin.readlinedef solution(N, M, comps, edges): # 큐 / [환승 횟수, 노드, 거리] q = [[0..

https://www.acmicpc.net/problem/14431다익스트라 알고리즘 문제입니다.다만 이동 거리가 소수인지 판정하기 위해 문제에서 나올 수 있는 최대 거리 이하인 모든 소수를 구한 뒤 마을 사이의 거리가 소수인 경우에만 그래프에 저장해 알고리즘을 돌리면 됩니다.import sysimport heapq as hqinput = sys.stdin.readline# 거리를 계산하는 함수def cal_dist(x1, y1, x2, y2): dx = x1-x2 dy = y1-y2 return pow(pow(dx, 2) + pow(dy, 2), 1/2)def solution(x1, y1, x2, y2, N, vils): # 마을 상에서 최대 거리 : [-3000, -3000] ~..

https://www.acmicpc.net/problem/22865다익스트라 알고리즘 문제입니다.친구들의 집을 모두 시작점으로 넣고 다른 노드들까지의 최단 거리를 구해준 뒤 그 중 가장 먼 노드를 골라 출력해주면 됩니다.import sysimport heapq as hqinput = sys.stdin.readlinedef solution(N, A, B, C, M, edges): # 그래프 graph = [[] for _ in range(N+1)] for D, E, L in edges: graph[D].append([E, L]) graph[E].append([D, L]) # 최단거리 리스트 min_dists = [float('inf') for _ ..

https://www.acmicpc.net/problem/13911다익스트라 알고리즘 문제입니다.시작점과 끝점을 어떻게 잡을지 고민일텐데 사실 크게 상관은 없습니다. 어느 경우든 두 번으로 구할 수 있습니다. 1. 집이 될 수 있는 위치 ~ 가게해당 경우는 집이 될 수 있는 모든 위치를 동시에 시작점으로 잡고 두 가게를 각각 다익스트라 알고리즘을 돌리면 됩니다. 2. 가게 ~ 집이될 수 있는 위치해당 경우는 역시 알고리즘을 두 번 돌릴텐데 각 가게마다 위치를 동시에 시작점으로 잡고 나머지 위치를 대상으로 다익스트라 알고리즘을 진행하면 됩니다. 결국 해당 문제의 핵심은 시작점마다 각각 알고리즘을 돌리는 것이 아닌 모든 지점을 시작점으로 알고리즘을 돌릴 수 있는가에 대한 것 같습니다. import sysim..

https://www.acmicpc.net/problem/23793다익스트라 알고리즘 문제입니다.x - y - z 경로로 이동하는 경우 (x - y) / (y - z) 경로를 따로 계산해 더해주면 됩니다.y를 거치지 않는 x - z 경로의 경우는 y 경로로 이동하는 모든 경우를 계산에서 제해주면 됩니다.import sysimport heapq as hqinput = sys.stdin.readline# 다익스트라def dijkstra(graph, s, e, b=None): # 큐 q = [[0, s]] # 최단거리 리스트 min_dists = [float('inf') for _ in range(N+1)] min_dists[s] = 0 # 순회 while q: ..

https://www.acmicpc.net/problem/2665다익스트라 알고리즘을 사용해 풀 수 있는 문제입니다. 이동 가능한 방향을 탐색할 때, 이동할 노드가 벽이 아니라면 해당 노드를 바꿀 필요가 없기 때문에 그대로 큐에 넣어주지만, 해당 노드가 벽이라면 우선 바꾸고 이동한 것으로 간주해 큐에 넣어줍니다. 이런 식으로 탐색을 진행하면 모든 노드를 최소 변환 횟수와 함께 탐색할 수 있습니다. 큐를 최소힙으로 사용하는 이유는 바꾼 횟수가 적은 순서로 탐색을 해주기 위함인데, 바꾼 횟수가 더 많고 같은 위치를 탐색할 경우 더 적은 횟수로 먼저 탐색했기 때문에 자동으로 걸러주기 때문입니다. 최소힙이 아닌 데크를 사용할 경우, BFS처럼 풀 수도 있지만 바꾼 횟수가 높은 탐색경우가 먼저 같은 위치에 도달하..

https://www.acmicpc.net/problem/18352다익스트라 문제입니다.다익스트라로 시작점에서 최단거리를 찾아주면 풀 수 있습니다.주의할 점이 있다면 시작 노드의 최단거리를 0 으로 시작하지 않으면 2 의 최단거리를 갖는 노드를 검색할 때 시작 노드도 포함될 수 있습니다.import sysimport heapq as hqinput = sys.stdin.readlinedef solution(N, M, K, X, edges): # 그래프 graph = [[] for _ in range(N+1)] for A, B in edges: graph[A].append(B) # 최단거리 목록 min_dists = [float('inf') for _ in range(..