[백준 BOJ][JAVA] 11725번: 트리의 부모 찾기

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

이번 문제는 트리의 부모를 찾는 문제!

언뜻 봤을 때는 되게 쉬워보였는데, 좀 짜증나는 문제였다

사실상 트리는 곁다리고 그래프 문제였기 때문..ㅎㅎ

 

문제 조건

 

 

문제 이해하기

결국 각 노드의 부모 노드를 찾으면 되는 문제이다!

그런데 입력 부분에서 조금 이해가 안 갔었다. 

 

트리의 노드는 항상 1이며, 루트 없는 트리가 입력으로 주어진다고 한다. 

그리고 입력으로는 트리 상에서 연결된 두 정점이 주어진다. 

예제 입력1을 따라가면서, 그림을 통해 다시 이해해보자!

 

입력으로는 

7 // 노드의 개수
1 6
6 3
3 5
4 1
2 4
4 7

이 주어진다. 

(1) 처음에 1 6이 주어진다. 

1이 6과 연결되어 있다는 것인데, 문제에서 루트는 항상 1이라고 했기 때문에

1의 자식 노드로 6을 넣어준다. 

 

(2) 6 3이 주어진다. 

6과 연결되려면 3을 6의 자식 노드로 넣는 수밖에 없다!

 

(3) 3 5가 주어진다.

위와 마찬가지로 5는 3의 자식 노드가 된다!

 

(4) 4 1이 주어진다.

1번과 똑같다. 루트는 항상 1이기 때문에,

4가 1과 연결되려면 4는 1의 자식 노드여야 한다.

 

(5) 2 4가 주어진다.

2와 4가 연결되려면?

당연히 2가 4의 자식노드가 되어야 한다.

 

(6) 4 7이 주어진다.

4와 7 연결? 4와 7이 연결되려면 7이 4의 부모노드거나 자식노드여야 하는데,

이미 4의 부모노드는 1로 확정이 되었다. 그러므로, 7은 4의 자식노드!

 

이제 트리를 다 구성했으며, 

2번 노드부터 차례대로 부모 노드를 출력하면 된다.

(나는 그냥 출력하면 된다고 생각했다. 그런데 아니었다.^^)

문제에서 2번 노드부터 차례대로 부모노드를 출력하라고 한다. 

나는 여기서 큰 착각을 했었다. 

파란색으로 적은 것처럼 노드의 번호를 매겨서, 2번 노드부터 부모 노드를 

1 1 6 4 4 5 이런 식으로 출력하면 된다고 생각했는데

문제가 그렇게 쉬울 리가 없지.. 이 방식이 전혀 아니었다.

(배고파서 정신이 나갔나보다. 문제 이해를 전혀 못 하고 있다..)

 

일단 출력값으로는

4
6
1
3
1
4

위의 값이 나와야하고, 이 값이 나오려면 트리에서 2를 찾아, 이 노드의 부모 노드인 4를 출력하고

3을 찾아, 부모 노드인 6을 출력

4를 찾아, 부모 노드인 1을 출력

5를 찾아, 부모 노드인 3을 출력

6을 찾아, 부모 노드인 1을 출력

7을 찾아, 부모 노드인 4를 출력해야 한다.

그러면 4 6 1 3 1 4으로, 알맞은 출력값이 나온다. 

아이디어 도출하기

트리를 어떤 식으로 구성해야 하는지 이해했고,

어떤 식으로 출력하는지도 이해했다.

근데 다 망했다

트리 만들고, 노드 하나하나 탐색해서 부모 노드 찾아서 했더니 시간 초과 나온다.

한마디로 위에 쓴 방법 아니라는 것!

지금까지 한 건 모두 삽질이었다! 행복하네..

 

DFS 써서 풀어야 한다..

최종 코드는 아래에 있는 것이다 (풀이는 나중에..)

 

 

문제 풀이 (코드)

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
	static int[] parents;
	static List<Integer>[] list;
	static boolean[] visit;
	static int n;
	
	private static void dfs(int v) {
		visit[v] = true;
		for(int i : list[v]) {
			if(!visit[i]) {
				parents[i] = v;
				dfs(i);
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		
		list = new ArrayList[n + 1]; parents = new int[n + 1];
		for(int i = 1; i <= n; i++) {
			list[i] = new ArrayList<>();
		}
		
		visit = new boolean[n+1];
		for(int i = 0; i < n - 1; i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();
			
			list[a].add(b); 
			list[b].add(a);
		}
		
		dfs(1);
		for(int i = 2; i <= n; i++) {
			System.out.println(parents[i]);
		}
			
		scan.close();
	}
}

개짜증나. . 나중에 풀이 추가하고 수정하면서 이 멘트도 지워야지..