import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static ArrayList<Integer>[] list;
static boolean[] visit;
static int[] parents;
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st ;
N = Integer.parseInt(br.readLine());
list = new ArrayList[N+1]; // 각 노드의 개수 + 1로 배열의 크기 정함
visit = new boolean[N+1]; // 해당 노드를 방문 여부를 확인할 배열
parents = new int[N+1]; // 각 인덱스의 값은 노드의 부모
for(int i = 0 ; i <= N; i++ ) { // 각 인덱스에 노드의 연결상태를 넣음
list[i] = new ArrayList<Integer>();
}
for(int i = 0; i< N-1; i++) {
st = new StringTokenizer(br.readLine());
int num1 = Integer.parseInt(st.nextToken());
int num2 = Integer.parseInt(st.nextToken());
list[num1].add(num2);
list[num2].add(num1);
}
for(int i = 1 ; i <= N;i++) {
if(!visit[i]) {
dfs(i);
}
}
for(int i = 2; i <= N;i++) { // 노드 2번부터 출력하기 위해 i = 2로
System.out.println(parents[i]);
}
}
static public void dfs(int num) {
if(visit[num]) {
return;
}
visit[num] = true;
for(int value : list[num]) {
if(!visit[value]) {
parents[value] = num;
dfs(value);
}
}
}
○ 문제 요약
트리의 루트를 1이라고 정하고 각 노드의 부모 노트를 출력해라.
○ 문제 풀이
이번 문제는 List를 N + 1의 크기로 만들어주고 다시 List 안에 List를 만드는 방법으로 풀었다.
말로 하면 이해가 더 어려우니 그림으로 보도록 하자.
예제 입력 1을 list에 넣었을 때, list는 아래와 같이 값이 들어가 있는 모습을 보인다.
그리고 dfs() 메소드를 실행하면
위와 같은 과정을 반복하면서 parents 배열에 값을 채워나간다.
그러면 아래와 같이 parents 배열의 값이 형성되는데
각 인덱스는 노드의 번호이고 각 인덱스의 값은 노드의 부모가 된다.
i가 2부터 배열을 출력하면
4
6
1
3
1
4
가 출력되어 문제에서 원하는 대로 출력되는 것을 알 수 있다.
○ 결과
'문제풀이 > 백준' 카테고리의 다른 글
백준 2178. 미로 탐색(JAVA) (0) | 2022.04.20 |
---|---|
백준 9372. 상근이의 여행(JAVA) (0) | 2022.04.18 |
백준 2667. 단지번호붙이기 (JAVA) (DFS) (0) | 2022.04.08 |
백준 1012. 유기농 배추(JAVA) (DFS) (0) | 2022.04.06 |
백준 2606. 바이러스 (JAVA) (0) | 2022.04.05 |