루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
DFS와 BFS 두 가지로 풀이해보았고, 앞으로의 응용문제들을 위한 기초문제라고 느껴졌다.
메모리는 BFS < DFS, 시간은 BFS > DFS.
import java.util.*;
import java.io.*;
public class Main {
static int N;
static int[] parent;
static boolean[] visited;
static ArrayList<Integer>[] graph;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
parent = new int[N+1];
visited = new boolean[N+1];
graph = new ArrayList[N+1];
for (int i = 0; i <= N; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < N-1; i++) {
st = new StringTokenizer(br.readLine(), " ");
int v = Integer.parseInt(st.nextToken());
int u = Integer.parseInt(st.nextToken());
graph[v].add(u);
graph[u].add(v);
}
visited[1] = true;
dfs(1);
StringBuilder sb = new StringBuilder();
for(int i = 2; i <= N; i++) {
sb.append(parent[i]).append("\n");
}
System.out.println(sb.toString());
}
public static void dfs(int u) {
for(int v : graph[u]) {
if(!visited[v]) {
parent[v] = u;
visited[v] = true;
dfs(v);
}
}
}
}
import java.util.*;
import java.io.*;
public class Main {
static int N;
static ArrayList<Integer>[] graph;
static Queue<Integer> queue;
static boolean[] visited;
static int[] parent;
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];
queue = new LinkedList<>();
visited = new boolean[N + 1];
parent = new int[N + 1];
for (int i = 0; i <= N; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < N - 1; i++) {
st = new StringTokenizer(br.readLine(), " ");
int v = Integer.parseInt(st.nextToken());
int u = Integer.parseInt(st.nextToken());
graph[v].add(u);
graph[u].add(v);
}
queue.add(1);
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v : graph[u]) {
if (!visited[v]) {
visited[v] = true;
parent[v] = u;
queue.add(v);
}
}
}
StringBuilder sb = new StringBuilder();
for(int i = 2; i <= N; i++) {
sb.append(parent[i]).append("\n");
}
System.out.println(sb.toString());
}
}