[BAEKJOON] 11725 트리의 부모 찾기

문제 요약

• 알고리즘 분류: 트리, 탐색
• 난이도: Silver2
• 문제내용:
  • 루트가 1이라고 가정할때 2번 노드부터 N개까지의 부모노드를 출력해라.

• 사이트: https://www.acmicpc.net/problem/11725

1655번: 가운데를 말해요

문제풀이

 이번 문제는 트리의 활용과 트리의 탐색에 대한 내용을 알고있으면 풀수있다고 생각한다. 트리에 대한 자세한 설명은 여기에서 확인 해보면 된다.

문제 접근 방법

 일단 예제 1번을 그림 으로 대충 표현한다면 아래와 같다.

왼쪽은 문제상 그렸을때 오른쪽은 루트 1기준으로 그린 트리

 왼쪽것을 오른쪽으로 구도로 표현 하는 방법만 알면 쉽게 풀수가 있다. 그전에 알아야 될것이 level order 탐색 방법이다. 흔히 알고있는 bfs랑 구현이랑 거의 비슷하다. 큐에 시작 노드에 담아서 노드랑 연결된 데이터를 큐에 담아서 앞에 노드를 pop()연산해서 노드를 탐색 하는 방법이다. 그래서 이번 문제는 1부터 시작해서 level order로 탐색 한 다음 부모 노드를 저장할 배열이나 리스트에다가 탐색한 노드는 현재 노드에다가 저장만 하면된다.

정리

1.  각 노드랑 연결 되어 있는 노드랑 연관 되게 저장한다.
2. 1 부터 시작해서 level order을 탐색하고 탐색한 노드 인덱스에 현재 위한 노드를 저장한다.

Code

Python

 bfs탐색이나 level order 탐색할때 deque가 유용하게 쓰인다.

import sys
from collections import deque
input = sys.stdin.readline

def level_order(start):
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for i in tree[node]:
            if parent[i] == 0:
                parent[i] = node
                queue.append(i)
    
N = int(input())
tree = {i : [] for i in range(1, N + 1)}

parent = [0] * (N + 1)

for _ in range(N - 1):
    a ,b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
level_order(1)

for node in parent[2:]:
    print(node)

Java

 자바 보면 임포트 된 자료구조인데 Map방식으로 저장말고도 2차원 배열로 처리가 가능한데 그러면 코드가 길어질거 같아서 Map으로 구현 했다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
		
	static Map<Integer, ArrayList<Integer>> tree = new HashMap<Integer, ArrayList<Integer>>();
	static int[] parent;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		parent = new int[N + 1];
		StringTokenizer st;
		int a, b;
		for(int i = 1; i <= N; i++) {
			tree.put(i, new ArrayList<Integer>());
		}
		for(int i = 0; i < N - 1; i++) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			tree.get(a).add(b);
			tree.get(b).add(a);
		}
		find_parent(1);
		StringBuilder sb = new StringBuilder();
		for(int i = 2; i <= N; i++) {
			sb.append(parent[i]).append("\n");
		}
		System.out.println(sb.toString());
		
	}
	
	public static void find_parent(int start) {
		for(int node : tree.get(start)) {
			if(parent[node] == 0) {
				parent[node] = start;
				find_parent(node);
			}
		}
	}

}