[백준] 11725. 트리의 부모 찾기 (자바 JAVA)

[ 문제 ]  [백준] 11725. 트리의 부모 찾기 (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

---

# 접근 방법 및 풀이 

 

• 트리구조를 떠올리며 BFS로 풀었다. DFS로도 가능. 노드의 부모를 찾는 문제다.
• 트리라고하니 이진트리라고 한정지었는데 틀렸다. 문제에 이진트리라는 조건도 없고 그냥 연결된 노드 정보만 있다.
• 다만, 루트노드가 1이기 때문에 루트노드부터 연결된 노드를 탐색하며 부모노드를 찾을 수 있다.
• 현재 노드가 어디 노드로부터 왔는지 찾으면 된다.
• 예제 1번에 "1 6" 이라고 되어있는데, 6번 노드는 1번노드로 부터 왔기 때문에 1번이 부모노드가 된다.
• 문제에 주어진 연결 정보를 인접리스트로 노드와 노드의 양방향 연결을 표현해주고 1번 루트노드부터 BFS를 돌려 풀었다.
• 자세한건 코드참조

# 주의할 점 

 

• 트리가 이진트리라고 생각하면 안됨. 그냥 연결된 그래프구조다.

 

JAVA 코드

package Silver;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class bj11725_트리의부모찾기 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());
		List<Integer> list[] = new ArrayList [N+1];
		for (int i = 0; i < list.length; i++) {
			list[i] = new ArrayList<Integer>();
		}
		for (int i = 0; i < N-1; i++) {
			StringTokenizer st = new StringTokenizer(in.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			list[a].add(b);
			list[b].add(a);
		}
		boolean visit[] = new boolean[N+1];
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(1);
		visit[1] = true;
		int ans[] = new int [N+1];
		while(!queue.isEmpty()) {
			Integer num = queue.poll();
			for (Integer i : list[num]) {
				if(!visit[i]) {
					visit[i] = true;
					ans[i] = num;
					queue.add(i);
				}
			}
		}
		for (int i = 2; i < ans.length; i++) {
			System.out.println(ans[i]);
		}
	}
}

 

 

 

REVIEW

처음에는 문제가 잘 이해가 안되었는데, 이진트리라고 머릿속으로 한정지어서 그런 것 같다. 

주어진 문제대로 이해하고 풀자.