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

트리의 부모 찾기 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

100911

46107

32300

43.274%

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

예제 입력 1 복사

7
1 6
6 3
3 5
4 1
2 4
4 7

예제 출력 1 복사

4
6
1
3
1
4

예제 입력 2 복사

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

예제 출력 2 복사

1
1
2
3
3
4
4
5
5
6
6

 

 

package 문제11725트리의부모찾기;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main2 {
	static List<Integer>[] arr;
	static boolean[] visited;
	static int[] parent;
	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("res/문제11725트리의부모찾기.txt"));
		// 마당에서 탈출할 수 있는 칸은 어떤 영역에도 속하지 않는다.
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		StringTokenizer st = new StringTokenizer(s);
		int N = Integer.parseInt(st.nextToken());
		arr = new ArrayList[N+1];
		visited = new boolean[N+1];
		parent = new int[N+1];
		for (int i = 0; i<N+1; i++) {
			arr[i] = new ArrayList<>();
		}
		for (int i = 0; i<N-1; i++) {
			s = br.readLine();
			st = new StringTokenizer(s);
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			arr[A].add(B);
			arr[B].add(A);
		}
		
		dfs(1);
		for (int i=2; i<N+1; i++) {
			System.out.println(parent[i]);
		}
		

	}
	public static void dfs(int A) {
		Stack<Integer> stack = new Stack<>();
		stack.add(A);
		visited[A] = true;
		while (!stack.isEmpty()) {
			int num = stack.pop();
			for (int i : arr[num]) {
				if (!visited[i]) {
					parent[i] = num;
					stack.add(i);
					visited[i] = true;
				}
			}
		}
	}

}

 

 

 

이런 트리 문제는 자식 노드를 하나하나 탐색하면서 부모를 설정하는 것보다, 한 번의 탐색(DFS or BFS)으로 모든 부모를 한 번에 찾아서 저장하는 게 더 효율적이다! 🚀🔥

---

📌 핵심 원리 정리

✅ 1. "부모를 한 번에 찾는다"는 게 무슨 뜻?

• 처음부터 모든 노드의 부모를 각각 찾으려고 하면 비효율적
• 대신, BFS나 DFS를 한 번 실행하면서 한 번에 모든 부모를 저장
• 즉, 부모를 개별적으로 찾는 게 아니라, 한 번에 "미리 계산"해둔다!

💡 이 접근법을 쓰면, 트리의 부모를 O(N) 시간에 찾을 수 있음!
(각 노드를 한 번씩만 방문하면 되니까!)

---

✅ 2. "한 번에 찾는다"를 코드로 표현하면?

✔ BFS 사용

Queue<Integer> queue = new LinkedList<>();
queue.add(1);  // 루트부터 시작
visited[1] = true;

while (!queue.isEmpty()) {
    int cur = queue.poll(); // 현재 노드 (부모 역할)

    for (int next : arr[cur]) { // 연결된 노드들 확인
        if (!visited[next]) { // 아직 방문 안 했다면?
            visited[next] = true;  
            parent[next] = cur;  // 🔥 부모를 한 번에 저장!
            queue.add(next);  // 다음 탐색을 위해 큐에 추가
        }
    }
}

✔ DFS 사용

public static void dfs(int cur) {
    visited[cur] = true; // 방문 체크

    for (int next : arr[cur]) { // 연결된 노드들 확인
        if (!visited[next]) { // 아직 방문 안 했다면?
            parent[next] = cur;  // 🔥 부모를 한 번에 저장!
            dfs(next);  // 재귀 호출 (다음 노드 탐색)
        }
    }
}

---

✅ 3. "각각 찾는 방식"과 "한 번에 찾는 방식" 비교

방법 탐색 방식 시간복잡도 효율성

❌ 각각 찾는 방식	dfs(i)를 모든 노드에 대해 실행	O(N^2) (매번 새 탐색)	느림 (시간 초과 위험!)
✅ 한 번에 찾는 방식	BFS/DFS 한 번만 실행	O(N) (각 노드를 1번만 방문)	빠름 (최적화됨!)

💡 "각각 찾는 방식"은 한 번 찾을 때마다 탐색이 반복되므로 시간이 오래 걸림!
💡 "한 번에 찾는 방식"은 탐색을 딱 한 번만 해서 훨씬 빠름!

---

📌 결론

👉 이런 트리 문제는 자식 노드를 하나씩 확인하며 부모를 설정하는 것보다,
한 번의 탐색(BFS/DFS)으로 모든 부모를 미리 찾아 저장하는 것이 더 효율적이다! 💡🚀

이제 비슷한 문제 나오면 무조건 "한 번에 찾는 방식"을 떠올리자! 😆🔥