[ 트리 ] 트리🎄(백준 11725)

 트리

트리는 노드와 에지로 연결된 그래프의 특수한 형태이다.

• 순환 구조(사이클)를 지니고 있지 않고, 1개의 루트 노드가 존재한다.
• 루트 노드를 제외한 노드는 단 1개의 부모 노드를 가진다.
• 트리의 부분 트리 역시 트리의 모든 특징을 따른다.

 

💡 트리의 핵심 이론

구성 요소	설명
노드	데이터의 index와 value를 표현하는 요소
에지	노드와 노드의 연결 관계를 나타내는 선
루트 노드	트리에서 가장 상위에 존재하는 노드
부모 노드	두 노드 사이의 관계에서 상위 노드에 해당하는 노드
자식 노드	두 노드 사이의 관계에서 하위 노드에 해당하는 노드
리프 노드	트리에서 가장 하위에 존재하는 노드(자식 노드가 없는 노드)
서브 트리	전체 트리에 속한 작은 트리

 

 

💡 코딩테스트에서 트리가 나오는 유형

① 그래프로 푸는 트리(DFS, BFS)

② 트리만을 위한 문제(이진 트리, 세그먼트(index) 트리, 최소공통조상)

 

 

 

 11725 : 트리의 부모 찾기

문제

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

 

입력

 

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

 

출력

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

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

 

문제 풀이

• 인접 리스트 자료구조를 사용한다.
• 1번 노드부터 DFS로 탐색 -> 자식노드로 가기 전에 현재 노드가 다음 번에 탐색한 노드의 부모노드

 

실행 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class P11725_tree {
    static ArrayList<Integer>[] list;
    static int[] parent;
    static boolean[] visited;
    static int N;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt(); //노드의 갯수
        parent = new int[N+1]; //부모를 저장하는 배열
        visited = new boolean[N+1];
        Arrays.fill(visited, false); //모두 방문 안한걸로 채움
        list = new ArrayList[N+1];
        for (int i = 1; i <= N; i++) { //인접리스트
            list[i] = new ArrayList<>();
        }

        // 인접리스트 데이터 저장
        for(int i=1;i<N;i++){
            int n1 = sc.nextInt();
            int n2 = sc.nextInt();
            list[n1].add(n2);
            list[n2].add(n1);
        }

        saveRoot();
        for(int i=2;i<=N;i++){
            System.out.println(parent[i]);
        }
    }

    private static void saveRoot() {
        for(int i=1;i<N;i++){
            if(!visited[i])
                DFS(i);
        }
    }

    private static void DFS(int i) {
        if(visited[i]) return; //방문한 노드일 때는 return
        visited[i] = true;
        for(int n : list[i]){
            if(!visited[n]){
                parent[n] = i;
                DFS(n);
            }
        }
    }
}