🔗 Problem Link 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net ❔Thinking 트리는 한 노드에서 다른 노드까지 가는 경로가 유일하다. 한 노드에서 가장 먼 노드는, 트리의 지름의 한 양 지점 중 하나이다. 💻Solution import sys import heapq input = sys.stdin.readline V = int(input()) tree = [[] for _ in range(V+1)] for _ in range(V): tmp = list(map(int, input..

다익스트라 알고리즘 한 지점에서, 다른 모든 지점까지의 최단 경로를 찾는 알고리즘 GPS, 라우팅 프로토콜 등에서 사용된다. A -> C 거리가 A -> B -> C 거리보다 짧다면 A에서 C까지의 최단 경로를 수정하는 방식이다. heapq를 활용한 구현 1~2 : 모든 정점까지의 거리를 INF로 초기화 하고, 출발점(start) 자기 자신까지의 거리는 0으로 초기화한다. 3 : 거쳐가는 거리보다 바로 가는 거리가 짧다면 업데이트 하지 않는다. 4 : 거쳐가는 거리가 더 짧은 경우, 거리를 업데이트 한다. queue에 (거리, 도착 정점) 순으로 넣어야 거리가 짧은 정점부터 확인할 수 있다. def dijkstra(start): distance = [int(1e9)] * (N+1) # 1 distance..

🔗 Problem Link 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net ❔Thinking NxN 크기의 공간이 주어질 때, (0,0)에서 출발해 (N-1, N-1)로 이동하는 최소 비용을 반환한다. 💻Solution import heapq INF = int(1e9) dx = [-1,1,0,0] dy = [0,0,-1,1] def dijkstra(x, y, graph): q = [] n = len(graph) heapq.heappush(q, (graph[x][y], x, y)) while ..

🔗 Problem Link 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 ❔Thinking 도시의 개수, 도로의 개수, 출발 도시의 번호가 주어질 때, 최단 거리가 k인 도시를 모두 출력한다. 💻Solution 1. BFS를 활용한 풀이 from collections import deque import sys input = sys.stdin.readline n, m, k, x = map(int, input().split()) graph ..