[백준] 11725번 - 트리의 부모 찾기

💎 문제 링크

11725번: 트리의 부모 찾기

 

📝 문제

 

✍🏻 입력 & 출력

🤔 풀기 전에 생각하기

트리의 인덱스 개념 정석으로

부모 노드는 자식 노드의 /2 인덱스

자식 노드는 부모 노드의 *2, *2+1으로 하려다 보니 배열의 크기가 엄청나게 커지게 된다.

 

고민하던 중 다른 분의 풀이를 참고해 이해하고 스스로 풀이

참고 블로그

 

✨ 풀이

Scanner와 BufferedReader는 메모리와 속도차이

Scanner가 아래, BufferedReader가 위

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {

    public static int[] parents; // 부모 노드를 저장할 배열
    public static ArrayList<Integer>[] list; // 각각의 노드에 대한 리스트를 생성할 배열
    public static int N; // 입력받는 수 N
    public static boolean[] isVisit; // 방문한 노드인지 확인 -> 또 방문하면 부모노드라는 뜻

    public static void main(String[] args) throws IOException {
//        Scanner scanner = new Scanner(System.in);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

//        N = scanner.nextInt();
        N = Integer.parseInt(br.readLine());
        parents = new int[N+1];
        isVisit = new boolean[N+1];
        list = new ArrayList[N+1]; // 배열의 크기를 정해주고

        for (int i = 1; i < N + 1; i++) {
            list[i] = new ArrayList<>(); // 배열마다 ArrayList 할당
        }

        for (int i = 0; i < N - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
//            int a = scanner.nextInt();
//            int b = scanner.nextInt();
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            list[a].add(b); // 1번노드 리스트에 6, 6번노드 리스트에 3
            list[b].add(a); // 6번노드 리스트에 1, 3번노드 리스트에 6
            /*
             * 최종 리스트
             * [1] - 6, 4
             * [2] - 4
             * [3] - 6, 5
             * [4] - 1, 2, 7
             * [5] - 3
             * [6] - 1, 3
             * [7] - 4
             */
        }

        dfs(1); // 재귀함수

        for (int i = 2; i < parents.length; i++) {
            /*
             * 0번 1번 인덱스는 출력안해도 되기 때문에 2부터 실행
             */
            System.out.println(parents[i]);
        }
    }

    public static void dfs(int index) {
        isVisit[index] = true; // 방문한 노드는 무조건 true

        for (int i : list[index]) { // i 값은 list[1]의 값 {6, 4}
            if (!isVisit[i]) { // isVisit[6], isVisit[4]는 아직 true로 안바꼈으니까 false, isVisit이 false여야 if문 실행
                parents[i] = index; 
                /*
                 * 현재 노드는 방문한적이 없기 때문에 붙어있는 노드가 부모노드
                 * parents[6]에 1번노드가 부모라는 의미로 값을 넣어줌
                 */
                dfs(i);
                /*
                 * dfs(6) 실행
                 * 
                 * 방문했으니까 isVisit[6] = true
                 * list[6]의 값들 {1, 3} 확인
                 * isVisit[1]은 이미 true이기 때문에 if문 실행 안함
                 * isVisit[3]은 false이기 때문에 if문 실행 후
                 * parents[3] = 6;
                 * 
                 * 또다시 dfs(3) 실행 반복
                 */
            }
        }
    }
}