트리의 간선 목록이 [u, v] 형태로 주어져 있다고 가정해 보겠습니다. 이는 노드 u와 노드 v 사이에 무방향 간선이 하나 존재한다는 의미입니다. 추가로 두 값 x와 y가 주어지며, 우리는 노드 x에 위치하고 상대방은 노드 y에 위치합니다. 첫 라운드에는 우리가 먼저 이동하고, 다음 라운드에는 상대방이 이동하는 식으로 번갈아 가며 게임이 진행됩니다. 단, 상대방은 자신의 차례에 이동하지 않고 제자리에 머무는 것을 선택할 수도 있습니다. 우리의 목표는 상대방을 반드시 잡기 위해 필요한 최소 라운드 수를 구하는 것입니다.
예를 들어 입력이 edges = [[0, 1], [0, 2], [1, 3], [1, 4]], x = 0, y = 3이라면 출력은 3이 됩니다. 첫 번째 차례에 우리가 노드 0에서 노드 1로 이동하고, 상대방이 현재 위치인 노드 3에 머무르기를 선택하면, 마지막으로 우리가 노드 3으로 이동하여 상대방을 잡을 수 있기 때문입니다.
접근 방법
이 문제는 너비 우선 탐색(BFS)을 두 번 수행하여 해결할 수 있습니다. 첫 번째 BFS는 우리의 시작 노드 x에서 각 노드까지의 최단 거리를 계산하고, 두 번째 BFS는 상대방이 잡히지 않고 도달할 수 있는 노드들을 탐색합니다. 전체 과정은 다음과 같습니다.
- N := 10^5 + 5
- 크기가 N인 배열 visited와 visited2를 선언하고 모든 값을 −1로 초기화합니다.
- N개의 노드에 대한 인접 리스트 graph를 생성합니다.
- edges의 각 간선 it에 대해 다음을 수행합니다.
- graph[it[u]]의 끝에 it[v]를 삽입합니다.
- graph[it[v]]의 끝에 it[u]를 삽입합니다.
- 큐 q를 하나 정의합니다.
- x를 큐에 삽입하고 visited[x] := 0으로 설정합니다.
- q가 빌 때까지 다음을 반복합니다.
- node := q의 첫 번째 원소를 꺼내고, q에서 해당 원소를 삭제합니다.
- graph[node]의 각 인접 노드 it에 대해 다음을 수행합니다.
- visited[it] == −1이면 다음을 수행합니다.
- visited[it] := visited[node] + 1
- it를 q에 삽입합니다.
- visited[it] == −1이면 다음을 수행합니다.
- y를 큐에 삽입하고, ret := 0, visited2[y] := 0으로 설정합니다.
- q가 빌 때까지 다음을 반복합니다.
- node := q의 첫 번째 원소를 꺼내고, q에서 해당 원소를 삭제합니다.
- ret := max(ret, 2 × visited[node] − 1)
- graph[node]의 각 인접 노드 it에 대해 다음을 수행합니다.
- visited2[it] == −1이고 visited2[node] + 2 < visited[it]이면 다음을 수행합니다.
- visited2[it] := visited2[node] + 1
- it를 q에 삽입합니다.
- visited2[it] == −1이고 visited2[node] + 2 < visited[it]이면 다음을 수행합니다.
- ret을 반환합니다.
여기서 핵심 조건은 visited2[node] + 2 < visited[it]입니다. 상대방이 어떤 노드로 이동한 직후 우리가 그 노드에 도달하기까지 충분한 거리가 남아 있어야, 즉 이동하더라도 당장 잡히지 않아야 그 노드로의 이동이 의미가 있기 때문입니다. 상대방이 도달할 수 있는 모든 노드를 탐색한 뒤, 그중 가장 오래 버틸 수 있는 지점을 기준으로 최소 라운드 수를 계산합니다.
C++ 구현 예제
다음 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int visited[N];
int visited2[N];
vector<int> graph[N];
class Solution {
public:
int solve(vector<vector<int>>& edges, int u, int v) {
memset(visited, -1, sizeof visited);
memset(visited2, -1, sizeof visited2);
for (int i = 0; i < N; i++)
graph[i].clear();
for (auto& it : edges) {
graph[it[0]].push_back(it[1]);
graph[it[1]].push_back(it[0]);
}
queue<int> q;
q.push(u);
visited[u] = 0;
while (!q.empty()) {
int node = q.front();
q.pop();
for (auto& it : graph[node]) {
if (visited[it] == -1) {
visited[it] = visited[node] + 1;
q.push(it);
}
}
}
q.push(v);
int ret = 0;
visited2[v] = 0;
while (!q.empty()) {
int node = q.front();
q.pop();
ret = max(ret, 2 * (visited[node]) - 1);
for (auto& it : graph[node]) {
if (visited2[it] == -1 && visited2[node] + 2 <
visited[it]) {
visited2[it] = visited2[node] + 1;
q.push(it);
}
}
}
return ret;
}
};
int solve(vector<vector<int>>& edges, int u, int v) {
return (new Solution())->solve(edges, u, v);
}
int main(){
vector<vector<int>> edge = {{0, 1},{0, 2},{1, 3},{1, 4}};
int x = 0, y = 3;
cout << solve(edge, x, y);
}
입력
[ [0, 1], [0, 2], [1, 3], [1, 4] ], 0, 3
출력
3
복잡도 분석
시간 복잡도: O(N) — 노드의 개수에 비례하여 두 번의 BFS를 수행합니다.
공간 복잡도: O(N) — 인접 리스트와 방문 여부 배열을 저장하는 데 노드 수에 비례하는 메모리가 필요합니다.