백준 JAVA 11725 트리의 부모 찾기 리뷰

문제풀이

먼저 트리는 인접행렬과 인접리스트를 통해 구현할 수 있는데 문제에서 N의 개수가 최대 10만이다. 인접행렬로 구현하면 10만*10만=100만의 공간을 차지하게 되므로 메모리가 4바이트라고 할때 40기가의 메모리를 필요하므로 메모리제한이 걸려있는 문제에서는 사용할 수 없다. 인접리스트를 사용해야한다.

 

트리라고 해서 트리구조를 코딩으로 만들 필요는 없다 그래서 문제에서 '루트없는 트리가 주어진다.'라고 말한 것같다. 그래프를 이용하면 되는 문제다.

문제에서 '이때, 트리의 루트를 1이라고 정했을 때,'라고 해서 루트가 없는데 루트가 있다고?? 헷갈렸다.

트리의 루트를 1이라고 정한건 시작정점을 알려주기 위해서인 것 같다. 

 

즉 트리구조를 코딩으로 만들지 말되 트리를 만든 후 트리 구조의 특징을 이용해서 그래프를 탐색하면 된다.

 

트리구조의 특징을 이용해서 풀어야 한다. 트리는 그래프의 특수한 형태로 어떤 정점의 인접한 정점은 반드시 부모노드 혹은 자식 노드라는 특징이 있다. 이를 이용하여 루트노드에서 탐색을 시작하면 특정 노드의 부모노드를 알 수 있다.

 

예제 1번을 토대로 해보면

루트노드 1번 방문

-인접 정점 4와 6

-1이 루트노드이므로 4, 6 전부 자식 노드

-반대로 말하면 4,6의 부모노드는 1

 

이런식으로 먼저 방문한 것이 부모노드가 되고 인접한 노드들이 자식노드가 된다.

각 노드의 부모를 구하는 프로그램을 작성해야하는데 먼저 방문한 것이 부모가 되기 때문에 루트노드부터 시작해서 차례대로 bfs/dfs를 하면 되는 문제였다. 

문제 풀때 예제 2는 이해되었는데 예제 1이 이해하기가 어려웠다. 그려서 직접 dfs/bfs 하니까 이해가 되었다.

 

 

출처

출처

 

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

public class Main {
    static ArrayList<Integer>[] tree;
    static boolean[] visited;
    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());

        tree=new ArrayList[N+1];
        visited=new boolean[N+1];
        parent=new int[N+1];

        for(int i=0; i<=N; i++){
            tree[i]=new ArrayList<>();
        }

        for(int i=1; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            tree[A].add(B);
            tree[B].add(A);
        }

        dfs(1);

        for(int i=2; i<=N; i++ ){
            System.out.println(parent[i]);
        }
    }
    static void dfs(int node){
        visited[node]=true;

        for(int next:tree[node]){
            if(!visited[next]){
                parent[next]=node;
                dfs(next);
            }
        }
    }
}