Dev_Diary

https://www.acmicpc.net/problem/2350최소 스패닝 트리 문제입니다.일반적인 최소 스패닝 트리가 아닌 최대 스패닝 트리를 만들어 타겟 노드 사이를 연결하는 노드 중 코스트가 최소인 엣지를 탐색해주면 됩니다.import sysfrom collections import dequeinput = sys.stdin.readline# union-finddef Union(group_list, n1, n2): # 그룹 g1 = Find(group_list, n1) g2 = Find(group_list, n2) # 두 그룹이 같으면 if g1 == g2: # 병합하지 않음 return False, group_list # 다르면 그룹..

https://www.acmicpc.net/problem/14921전형적인 투 포인터 문제입니다.상태값이 양수이면 0 으로 가까워지기 위해 값을 줄여야 하므로 r 포인터를 좌측으로 움직이고상태값이 음수이면 값을 늘려야 하므로 l 포인터를 우측으로 움직이며 값을 갱신하면 됩니다.import sysinput = sys.stdin.readlinedef solution(N, liquides): # 투포인터 l = 0 r = N-1 # 절댓값을 취할 시 최솟값이 되는 값 min_state_value = liquides[r] + liquides[l] # 순회 while l 0: # r 움직이기 r -= 1 # 0..

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/20010최소 스패닝 트리 문제입니다.최소 스패닝 트리는 크루스칼 알고리즘을 통해 구해주면 됩니다.그리고 그 중 가장 긴 경로를 구하는 경우는https://www.acmicpc.net/problem/1167해당 문제와 같은 경우입니다. 풀이는더보기임의의 노드를 골라 가장 먼 노드를 구한 뒤 해당 노드에서 다시 가장 먼 노드를 구하면 이는 가장 긴 경로가 된다는 내용입니다. 임의의 노드에서 가장 먼 노드를 고르면 트리의 가장 먼 두 노드 중 하나의 노드를 고르게 되므로 이를 두 번 진행하면 쉽게 구할 수 있습니다.import sysfrom collections import deque as dqinput = sys.stdin.readline## Uni..

https://www.acmicpc.net/problem/9344최소 스패닝 트리 문제입니다.다만 최소 스패닝 트리를 완성할 필요는 없고 트리를 만드는 과정 중 p, q 가 병합되었는지만 판단하면 됩니다. 크루스칼 알고리즘은 그리디 알고리즘이기 때문에 연결된 노드가 중간에 다시 끊어지는 경우가 없으므로 연결되는 순간 바로 출력해주어도 무관합니다.import sysinput = sys.stdin.readline## Union-Find# Finddef Find(group_list, node): # 자신이 그룹의 대표가 아니면 if group_list[node] != node: # 재귀적으로 재탐색 group_list[node] = Find(group_list, group_..

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: ..