[BAEKJOON] 백준 그래프 11725:: 트리의 부모 찾기

 

💬  문제 설명

루트 없는 트리가 주어진다. 이때, 트리의 루트를 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

​

💻  Main.java

• 처음에는 문제이름을 보고 트리로 푸는지 알고 아무 의심없이 트리로 풀었다.
• 하지만 이 문제는 트리로 풀면 시간초과가 떠, DFS나 BFS로 풀이해야한다... ㅠ
• 아래 코드는 트리로 푼 방법과, 방법 모두 올렸다.

트리로 푼 방법 (시간 초과)

/* 백준 그래프 - 11725 :: 트리의 부모 찾기 */

import java.util.*;
import java.io.*;

// 노드
class Node { 
	public int data; 
	Node lt, rt, ut;
	
	Node (int data){ 
		this.data = data;
	} 
	Node (int data, Node ut){ 
		this.data = data;
		this.ut = ut;
	} 
}
	
class Tree{
	Node root = new Node (1);
	StringBuilder sb = new StringBuilder();

	// 입력
	void add(Node root, int a, int b) {
		// 노드가 비어있으면 종료
		if(root == null) return;
		else if(root.data == a) { // 찾고 있던 노드를 찾으면 정보 입력
			if(root.rt == null)
				root.rt = new Node(b, root);
			else
				root.lt = new Node(b, root);
		}
		else if(root.data == b) {
			if(root.rt == null)
				root.rt = new Node(a, root);
			else
				root.lt = new Node(a, root);
		}
		else { // 왼쪽 포인터, 오른쪽 포인터로 노드 찾기
			add(root.lt, a, b);
			add(root.rt, a, b);
		}
	}
	
	void search(Node root, int a) {
		if(root == null) return;
		if(root.data == a) { // 찾고 있던 노드를 찾으면 정보 입력
			sb.append(root.ut.data).append('\n');
		}
		else {
			search(root.lt, a);
			search(root.rt, a);
		}
	}
	
	void print(int n) { // 2 ~ n까지 부모 노드출
		for(int i = 2; i <= n; i++) {
			search(root, i);
		}
		
		System.out.println(sb);
	}
}

public class Main {		
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
				
		// 트리 정보 입력
		Tree tree = new Tree();
		for(int i = 0; i < n - 1; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			tree.add(tree.root, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}
		
		tree.print(n);
		
		br.close();
	}
}

 

DFS, ArrayList 배열을 이용한 방법

/* 백준 그래프 - 11725 :: 트리의 부모 찾기 - dfs */

import java.util.*;
import java.io.*;

public class Main {
	static List<Integer>[] list;
	static int[] parent;
	static boolean[] check;
	static int n;
	
	static void dfs(int l) {
		// 중복 체크
		check[l] = true;
		
		// 가장 처음에 나오는 값이 무조건 부모
		for(int i : list[l]) {
			// 중복 검사
			if(!check[i]) {
				parent[i] = l;
				dfs(i);
			}
		}
	}
	
	@SuppressWarnings("unchecked")
	public static void main(String[] args) throws IOException{
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();

		list =  new ArrayList[n + 1];
		parent = new int[n+1];
		check = new boolean[n+1];
		
		// ArrayList 배열생성
		for(int i = 1; i <= n; i++) {
			list[i]  = new ArrayList<>();
		}
		
		// 노드 정보 입력
		for(int i = 0; i < n -1; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			
			list[a].add(b);
			list[b].add(a);
		}
		
		dfs(1);
		
		for(int i = 2; i <= n; i++) System.out.println(parent[i]);
		sc.close();
	}
}