[백준 11725: JAVA] 트리의 부모 찾기/ 트리, DFS

개요

 

이 문제는 처음에 입력받은 순서대로 부모 노드 값을 저장하여 풀이하였는데 

이렇게 푼 경우 누가 부모노드이고 누가 자식 노드인지 판별을 할 수 없는 문제가 발생하였다.

 

결국에는 입력받은 노드와 간선에 대한 정보를 인접리스트로 초기화하고

DFS를 이용하여 모든 경로를 탐색하며 부모노드 정보를 저장하여 풀이하였다.

 

기본적으로 DFS에 대한 이해가 바탕이 되어야 한다. 따라서 DFS에 대한 이해도가 낮다면 아래의 문제와 풀이를 먼저 보는 것을 추천한다.

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

2020/01/30 - [알고리즘/백준] - [백준 2667 : JAVA] 단지번호붙이기 / DFS

[백준 2667 : JAVA] 단지번호붙이기 / DFS

 

문제

 

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

 

입력

 

 

코드

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();
    static List<Integer> list[];

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());

        list = new ArrayList[N + 1];
        int parent[] = new int[N + 1];
        boolean isVisit[] = new boolean[N + 1];

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

        // 인접행렬 초기화
        for(int i = 1; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());

            // num1, num2 각각 이어져 있는 노드를 추가한다.
            list[num1].add(num2);
            list[num2].add(num1);
        }

        Stack<Integer> stack = new Stack<>();

        // 시작 노드 추가
        stack.push(1);
        isVisit[1] = true;

        // DFS
        while(!stack.isEmpty()){
            int start = stack.pop();

            for(int i = 0 ; i < list[start].size(); i++){
                int end = list[start].get(i);

                if(isVisit[end] == false) {
                    parent[end] = start;
                    stack.push(end);
                    isVisit[end] = true;
                }
            }
        }

        // 2번 노드 부터 부모노드를 출력한다.
        for(int i = 2; i <= N; i++) sb.append(parent[i] + "\n");

        bw.write(sb.toString());
        bw.close();
        br.close();
    }
}