Dev_Diary

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 다익스트라를 여러 번 사용해 풀 수 있습니다. #include #include #include #include #include using namespace std; /* 다익스트라를 세번 사용 */ // 다익스트라 int dijkstra(array tree, int N, int start, int end) { // 시스템상 최대 거리 int max_di..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 다익스트라 알고리즘을 사용해 풀 수 있습니다. #include #include #include #include #include using namespace std; /* 다익스트라 함수를 사용 */ array dijkstra(array tree, int K, int V) { // 시스템상 최대 수 한계 const int max_num = 3000001; // ..

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 아무 노드에서 가장 먼 노드와 해당 노드에서 가장 먼 노드의 길이를 탐색하면 풀 수 있는 문제입니다. 어떤 노드에서 가장 먼 노드를 탐색하면 이는 지름의 양 끝점 중 한 점에 해당하므로 타당한 풀이법 이라고 할 수 있습니다. import heapq import sys input = sys.stdin.readline def solution(n, data_list): # 다익스트라..

https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 최종 노드까지 걸리는 시간을 구하는 문제이므로 다익스트라 알고리즘을 통해 풀 수 있었습니다. from collections import deque import heapq import sys input = sys.stdin.readline def solution(n, d, c, dependency_list): # BFS, 다익스트라랑 비슷함 # 트리 / tree[i] = [[i 의 자식 노드, 시간],..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 걸을 때는 가중치가 1, 순간이동 할 때는 가중치가 0인 트리 구조로 생각하고 다익스트라 알고리즘을 통해 풀면 쉽게 풀 수 있습니다. import heapq def solution(N, K): # 다익스트라 min_time = dijkstra(N, K) return min_time def dijkstra(start, end): # 최대시간 inf = float..

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 임의의 노드(A)에서 가장 멀리있는 노드(B)를 찾는다면 해당 노드(B)는 가장 멀리 떨어진 두 노드중 하나의 노드에 해당하게 됩니다. 그리고 해당 노드(B) 에서 가장 멀리 있는 노드를 찾는다면(C) B 노드와 C 노드는 가장 먼 두 점이 되므로 두 노드 사이의 거리를 출력해주면 됩니다. import heapq import sys def solution(V, data_list):..

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 플루이드-워셜 알고리즘을 써도 괜찮지만 결국 한 지점에서 다른 지점까지의 최소거리의 합을 구하면 되는 문제이기 때문에 다익스트라 알고리즘을 여러 번 써서 풀었습니다. import heapq def solution(N, M, data_list): # 트리 tree = [[] for _ in range(N+1)] for data in data_list:..