빵똥

https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 1. 접근 가장 기본적인 탐색이 각 노드마다의 거리를 누적하여 x ~ y까지 몇 번 이동해야 하는가? 를 물었다면 이번엔 각 간선마다 비용이 있어 그 비용을 누적하면 되는 문제다! DFS를 활용하여 각 정점까지의 거리를 누적하는 방법과 다익스트라 알고리즘을 활용하는 두 가지의 방법이 있는데 둘 다 구현해보도록 하자! 그림으로 살펴보자! 2번 정점에서 출발할 때의 예시이다. 그림 속 표를 글로 쓰면 2번 정점에서 1번 정점까지의 비용 = 2 2..

https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 1. 접근 최초 접근 방법을 생각해내기까지 시간이 오래 걸렸지만 알아낸 이후부터는 비교적 쉽게 풀어낸 문제다! 저번 오리 문제와 마찬가지로 루트에서부터 내려가는 것이 아닌 공통 조상을 찾아야 하는 두 노드로부터 시작해보자! 예제 속 두 개의 케이스 중 첫 번째 케이스를 그림으로 보면 다음과 같다. 이 때, 순서에 상관은 없지만 7이 먼저 루트를 ..

https://www.acmicpc.net/problem/15900 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 1. 접근 DFS로 접근 시 인접 리스트를 사용하니 O(V + E) == O(500,000 + 499,999) = 1,000,000로 시간 초과 없이 풀 수 있다! 게임의 규칙을 살펴보면 각 말단 노드의 개수 = 말의 수이며 한 턴에 한 번씩 현재 노드의 부모 노드로 이동한다. 또한 게임에서 이기려면 순서가 먼저인 성원이 차례에 마지막 말을 루트로 이동시켜야 한다. 예제 3번을 그림으로 보면 말단..