문제 :
https://www.acmicpc.net/problem/11725
접근 :
- 입력되는 정보로 그래프를 작성
- 루트가 1 이므로 DFS를 통하여 1부터 인접한 노드의 부모 노드를 현재 수로 등록한다.
- 만약 인접 노드가 자신의 부모 노드일 경우 DFS를 실행하지 않는다.
- 부모 노드를 모두 등록하면 2부터 자신의 부모 노드를 출력한다.
코드 구현 :
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class Main {
private static ArrayList<Integer>[] adj;
private static int[] parents;
static void dfs(int now){
for(int n : adj[now]){
if(parents[now] == n) continue;
parents[n] = now;
dfs(n);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
String[] inputs;
adj = new ArrayList[n+1];
for (int i = 1; i <= n; i++) adj[i] = new ArrayList<>();
parents = new int[n+1];
int a, b;
for(int i = 1 ; i < n ; i++) {
inputs = br.readLine().split(" ");
a = Integer.parseInt(inputs[0]);
b = Integer.parseInt(inputs[1]);
adj[a].add(b);
adj[b].add(a);
}
dfs(1);
for(int i = 2; i <= n ; i++) sb.append(String.format("%d%n", parents[i]));
System.out.println(sb);
br.close();
}
}
'JAVA > Coding Test' 카테고리의 다른 글
[JAVA] 백준 1068 트리_트리 (0) | 2024.06.28 |
---|---|
[JAVA] 프로그래머스 단속카메라_최소힙 (0) | 2024.06.27 |
[JAVA] 백준 2688 줄어들지 않아_DP (0) | 2024.06.26 |
백준 9465 스티커_DP (0) | 2024.06.26 |
[JAVA] 백준 1520 내리막길_DP (0) | 2024.06.25 |