COMITO

문제 무방향 그래프가 주어질 때, 정점 1번에서 정점 N번으로 가는 최단거리를 구하려 하는데, 그 과정에서 두 개의 정점을 반드시 거쳐야 한다. 한 번 방문했던 정점을 또 다시 방문하는 것도 허용하고, 간선도 마찬가지로 여러번 방문하는 것을 허용한다고 할 때, 1번에서 N번으로 가는 “특정한" 최단거리를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. ( 4 ≤ N ≤ 1,000, 1 ≤ M ≤ N*(N-1)/2 ) 둘째 줄부터 간선의 정보가 주어진다. 각 줄은 두 개의 숫자 a, b, c로 이루어져 있으며, 이는 정점 a와 정점 b가 가중치 c인 간선으로 연결되어 있다는 의미이다. 마지막 줄에는 반드시 거쳐야 하는 두 정점 A, B가 주어진다. ( 1 ≤ ..

문제 트리가 주어지고, 두 노드 X, Y가 주어질 때, 이 두 노드 사이의 거리를 출력하는 프로그램을 작성하시오. 트리에서는 두 노드를 잇는 경로가 유일하기 때문에, 정답은 항상 유일하다는 것을 참고한다. 예를 들어, 다음과 같은 트리에서 노드 3, 노드 6 사이의 거리는 4이다. 입력 첫 번째 줄에 트리의 노드 개수 n, 두 노드 X, Y의 번호가 주어진다. ( 0 ≤ X, Y ≤ n < 1000 ) 두 번째 줄부터 트리의 간선 정보가 주어진다. 각 줄은 2개의 숫자 a, b로 이루어지며, 이는 노드 a가 노드 b의 부모노드라는 것을 의미한다. 루트는 노드 0이라고 가정한다. 출력 두 노드 X, Y 사이의 거리를 출력한다. 예제 입력 11 3 6 0 1 0 2 1 3 1 4 1 5 2 6 2 10 6 ..

문제 트리의 높이는 루트로부터 가장 멀리 떨어진 노드와의 거리로 정의된다. 예를 들어, 아래의 트리에서 0번 노드가 루트라고 하면, 7번 노드까지의 거리가 가장 멀고, 그 거리는 3이다. 따라서 이 트리의 높이는 3이 된다. 트리가 주어질 때, 그 트리의 높이를 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에 트리의 노드 개수 n, 그리고 루트노드의 번호 r이 주어진다. ( 1 ≤ n ≤ 100, 0 ≤ r ≤ n - 1 ) 두 번째 줄부터 트리의 간선 정보가 주어진다. 각 줄은 2개의 숫자 a, b로 이루어지며, 이는 a번 노드와 b번 노드가 연결되어 있다는 뜻이다. 각 노드의 번호는 0 ~ n-1까지 존재한다. 또한, 연결이 되지않은 노드는 없다. 출력 트리의 높이를 출력한다. 예제 입력 8 0 ..

최소 신장 트리의 이해 1. 신장 트리 란? Spanning Tree, 또는 신장 트리 라고 불리움 (Spanning Tree가 보다 자연스러워 보임) 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프 신장 트리의 조건 본래의 그래프의 모든 노드를 포함해야 함 모든 노드가 서로 연결 트리의 속성을 만족시킴 (사이클이 존재하지 않음) 2. 최소 신장 트리 Minimum Spanning Tree, MST 라고 불리움 가능한 Spanning Tree 중에서, 간선의 가중치 합이 최소인 Spanning Tree를 지칭함 3. 최소 신장 트리 알고리즘 그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘이 존재함 대표적인 최소 신장 트리 알고리즘 Kruskal’s algorithm (크루..

문제 그래프와 출발점, 도착점이 주어질 때 출발점에서 도착점까지 이동하기 위한 최단거리를 출력하는 프로그램을 작성하시오. 예를 들어, 아래 그림에서 출발 정점이 0, 도착 정점이 10이라고 할 때, 최단거리는 3이다. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. ( 1 ≤ N ≤ 10,000, 1 ≤ M ≤ 1,000,000 ) 둘째 줄부터 간선의 정보가 주어진다. 각 줄은 두 개의 숫자 a, b로 이루어져 있으며, 이는 정점 a와 정점 b가 연결되어 있다는 의미이다. M+1 번째 줄에 대하여 출발점과 도착점의 정점 번호가 주어진다. 정점의 번호는 0번부터 N-1번까지이다. 출력 출발점에서 도착점까지 이동하기 위한 최단거리를 출력한다. 예제 입력 11 14 0 1 0 2 1 2 1 4 ..

- 하나의 정점에서 모든 정점까지 최단 거리를 구하는 알고리즘(간선의 가중치가 양수일 때만) https://people.ok.ubc.ca/ylucet/DS/Dijkstra.html Dijkstra Visualization people.ok.ubc.ca a와 b 사이의 최단 경로를 찾는 데이크스트라의 알고리즘이다. 가장 낮은 값을 가진 방문하지 않은 꼭짓점을 선택하고, 방문하지 않은 각 인접 노드와의 거리를 계산하고, 작을 경우 인접 거리를 업데이트한다. 이 그림에서는 꼭짓점에 도착하면 빨간색으로 표시했다. 탐색 알고리즘 그래프 시간복잡도 O(|E|+|V|log|V|)} 출처 : 위키백과 #코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24..

- Node와 Branch를 이용해서 사이클을 이루지 않도록 구성한 데이터 구조 - 이진트리 : 노드의 최대 Branch가 2인 트리 - 이진탐색트리(Binary Search Tree, BST) : 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가진다. #코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82..

문제 트리의 노드 X에 대하여 “조상"을 정의할 수 있다. X의 “조상"이란, 루트까지 올라가는 중에 만나는 모든 노드를 말한다. 예를 들어, 아래와 같이 트리가 주어질 경우, 노드 8의 “조상"은 노드 0, 노드 2, 노드 6이 된다. 두 노드 X, Y의 공통 조상이란, X와 Y가 공통으로 갖는 조상을 말한다. 예를 들어, 노드 7과 노드 10의 공통조상은 노드 2, 노드 0이 된다. 가장 가까운 공통 조상이란, X와 Y가 공통으로 갖는 조상들 중에서 X, Y와 가장 가까운 조상을 말한다. 예를 들어, 노드 7과 노드 10의 가장 가까운 공통 조상은 노드 2가 된다. 트리가 주어지고, 두 노드 X, Y가 주어질 때, 가장 가까운 공통 조상을 찾는 프로그램을 작성하시오. 입력 첫 번째 줄에 트리의 노드 ..

문제 루트가 0인 이진트리가 주어질 때, 이를 전위순회, 중위순회, 후위순회한 결과를 각각 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에 트리의 노드 개수 n이 주어진다. ( 1 ≤ n ≤ 100 ) 두 번째 줄부터 트리의 정보가 주어진다. 각 줄은 3개의 숫자 a, b, c로 이루어지며, 그 의미는 노드 a의 왼쪽 자식노드가 b, 오른쪽 자식노드가 c라는 뜻이다. 자식노드가 존재하지 않을 경우에는 -1이 주어진다. 출력 첫 번째 줄에 전위순회, 두 번째 줄에 중위순회, 세 번째 줄에 후위순회를 한 결과를 출력한다. 예제 입력 6 0 1 2 1 3 4 2 -1 5 3 -1 -1 4 -1 -1 5 -1 -1 예제 출력 0 1 3 4 2 5 3 1 4 0 2 5 3 4 1 5 2 0 #코드 1 2 3 ..