문제
N개의 노드로 이루어진 트리에서 M개의 노드 쌍에 대해 두 노드 사이의 거리를 구하라.
입력
첫째 줄에 N, M, 이후 N-1개의 간선 (노드, 노드, 거리), 이후 M개의 쿼리가 주어진다.
출력
각 쿼리에 대해 두 노드 사이의 거리를 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 2 2 1 2 4 3 2 1 4 3 1 2 3 2 | 2 7 |
풀이
각 쿼리마다 DFS로 출발 노드에서 목표 노드까지의 경로 거리를 구한다.
- 인접 리스트와 비용 행렬로 트리를 구성한다
- 각 쿼리에서 DFS로 출발점부터 탐색하며 거리를 누적한다
- 목표 노드에 도달하면 flag를 세워 즉시 반환한다
- 경로가 아닌 방향은 백트래킹으로 거리를 되돌린다
핵심 아이디어: 트리에서 두 노드 사이의 경로는 유일하므로 DFS로 한 번의 탐색으로 거리를 구할 수 있다.
코드
package day449;
import java.io.*;
import java.util.*;
public class Day412BOJ1240노드사이의거리 {
static int N, M, cnt;
static int[][] cost;
static boolean flag;
static boolean[] visited;
static ArrayList<Integer>[] graph;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
graph = new ArrayList[N + 1];
cost = new int[N + 1][N + 1];
for (int i = 0; i < N + 1; i++) {
graph[i] = new ArrayList<Integer>();
}
for (int i = 0; i < N - 1; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
graph[u].add(v);
graph[v].add(u);
cost[u][v] = c;
cost[v][u] = c;
}
for (int i = 0; i < M; i++) {
visited = new boolean[N + 1];
st = new StringTokenizer(br.readLine());
int e1 = Integer.parseInt(st.nextToken());
int e2 = Integer.parseInt(st.nextToken());
cnt = 0;
flag = false;
dfs(e1, e2);
System.out.println(cnt);
}
}
static void dfs(int index, int goal) {
visited[index] = true;
for (int node : graph[index]) {
if (!visited[node]) {
cnt += cost[index][node];
if (node == goal) {
flag = true;
return;
}
dfs(node, goal);
if (flag)
return;
cnt -= cost[index][node];
}
}
}
}복잡도
- 시간: O(M * N) - 각 쿼리마다 DFS O(N)
- 공간: O(N²) - 비용 행렬