실버 2단계 문제였다.
앞서 풀었던 [백준] 1068번 트리 (JAVA)와 비슷한 유형이며, 난이도는 더 쉬운 문제이다.
1068번 문제를 풀 때 단뱡향 그래프를 사용하는 방법과 양방향 그래프를 사용하는 방법 두 가지 방법으로 나눠 풀었었다.
트리의 부모 찾기 문제도 부모를 찾기 위해서는 양방향 그래프로 접근해야 한다.
예제 입력 1을 그래프로 표현해보면
위와 같은 트리로 나타낼 수 있고, 출력은 2의 부모 4, 3의 부모 6, 4의 부모 1, 5의 부모 3, 6의 부모 1, 7의 부모 4 이므로 "4 6 1 3 1 4" 가 출력된다.
트리, DFS
import java.io.*;
import java.util.*;
public class Main {
static ArrayList<Integer>[] graph;
static int[] parent;
static boolean[] visited;
static int N, answer;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
graph = new ArrayList[N + 1];
parent = new int[N + 1];
visited = new boolean[N + 1];
for (int i = 0; i <= N; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < N-1; i++) {
//트리에서 간선의 수는 항상 노드의 수보다 1 적다
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
graph[a].add(b);
graph[b].add(a);
}
DFS(1);
StringBuilder sb = new StringBuilder();
for (int i = 2; i < parent.length; i++) {
sb.append(parent[i]).append("\n");
}
System.out.println(sb);
}
static void DFS(int v) {
visited[v] = true;
for (int current : graph[v]) {
if (!visited[current]) {
parent[current] = v;
DFS(current);
}
}
}
}