728x90
SMALL
https://www.acmicpc.net/problem/11725
11725번: 트리의 부모 찾기
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
www.acmicpc.net
처음에 문제 이해를 잘 못했었다.
정확히 무엇을 출력해야하는 것인지를 이해하지 못했었는데
알고보니 노드 2번부터 N번까지 차례대로 부모노드가 몇번인지를 알려달라는 것 이었다.
dfs를 적용하면 간단하게 해결할 수 있던 문제였다.
트리의 루트가 1번이기 때문에 dfs로 1번부터 순차적으로 방문을 체크하면서 확인해주면 된다.
import java.util.*;
import java.io.*;
class Main{
static boolean[] visited;
static int[] parent;
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int N = scan.nextInt();
visited = new boolean[N+1];
parent = new int[N+1];
ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
for(int i=0; i<N+1 ; i++){
lists.add(new ArrayList<>());
}
for(int i=0 ; i<N-1 ; i++){
int a = scan.nextInt();
int b = scan.nextInt();
lists.get(a).add(b);
lists.get(b).add(a);
}
dfs(1, lists);
for(int i=2;i<N+1 ; i++){
System.out.println(parent[i]);
}
}
public static void dfs(int index, ArrayList<ArrayList<Integer>> lists){
visited[index] = true;
for(int i : lists.get(index)){
if(!visited[i]){
parent[i] = index;
dfs(i,lists);
}
}
}
}
728x90
LIST
'Coding test > Baekjoon' 카테고리의 다른 글
[백준][JAVA] 1912번: 연속합 (0) | 2023.08.18 |
---|---|
[백준][JAVA] 2830번: 행성x3 - 3%에서 실패 해결... (0) | 2023.08.14 |
[백준][JAVA] 9012번: 괄호 (0) | 2023.08.14 |
[백준][JAVA] 10807번: 개수 세기 (0) | 2023.08.14 |
[백준][JAVA] 1158번: 요세푸스 문제 (0) | 2023.08.12 |