[JAVA] 백준 11725 트리

 

 

 

 

11725번: 트리의 부모 찾기

문제

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

풀이

해당 문제는 전체 노드들을 돌면서 상위 노드가 누구인지 체크하는 문제였다.

따라서 인접 리스트 형태의 그래프를 구현하고 DFS와 BFS로 탐색하여 문제를 해결했다.

📌 입력

        StringTokenizer st;
        for(int i=1; i<N-1; i++){
            st = new StringTokenizer(br.readLine(), " ");

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            A[a].add(b);
            A[b].add(a);
        }

인접 리스트를 만들고 양방향 그래프를 그려주었다.

📌 BFS

    static public void BFS(int a){
        Queue<Integer> q = new LinkedList<>();

        q.add(a);
        V[a] = true;
        while (!q.isEmpty()){
            int now = q.poll();
            for(int x : A[now]){
                if(!V[x]){
                    answer[x] = now;
                    V[x] = true;
                    q.add(x);
                }
            }
        }
    }

BFS로 탐색해주면서 now → x 일때, now값을 정답 배열 x에 넣어주었다.

📌 DFS

    static public void DFS(int a){

        V[a] = true;
        for(int x : A[a]){
            if(!V[x]){
                answer[x] = a;
                DFS(x);
            }
        }
    }

DFS로도 문제가 해결되었다.

DFS는 재귀적으로 돌기 전에 정답 배열 x에 a값(now)을 넣어주었다.

📌 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static ArrayList<Integer>[] A;
    static int[] answer;
    static boolean[] V;
    public static void main(String[] args) throws IOException {
        BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine())+1;

        A = new ArrayList[N];
        answer = new int[N];
        V = new boolean[N];

        for(int i=1; i<N; i++){
            A[i] = new ArrayList<>();
        }
        StringTokenizer st;
        for(int i=1; i<N-1; i++){
            st = new StringTokenizer(br.readLine(), " ");

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            A[a].add(b);
            A[b].add(a);
        }

        BFS(1);
        StringBuilder sb  = new StringBuilder();
        for(int i=2; i<N; i++){
            sb.append(answer[i]).append("\n");
        }

        System.out.println(sb);
    }

    static public void BFS(int a){
        Queue<Integer> q = new LinkedList<>();

        q.add(a);
        V[a] = true;
        while (!q.isEmpty()){
            int now = q.poll();
            for(int x : A[now]){
                if(!V[x]){
                    answer[x] = now;
                    V[x] = true;
                    q.add(x);
                }
            }
        }
    }

    static public void DFS(int a){

        V[a] = true;
        for(int x : A[a]){
            if(!V[x]){
                answer[x] = a;
                DFS(x);
            }
        }
    }

}

결과

DFS

BFS

DFS가 메모리 소모량은 더 크지만 속도가 빨랐고, BFS는 메모리는 적게 사용하지만 속도가 더 느렸다.