Java 백준 문제풀이 (30) 11725: 트리의 부모 찾기

 

 

간선만 던져주고 트리의 부모를 찾으라고 한다.

IQ 130 이상이면 정보를 구체화해서 머리 속에서 그릴 수 있다던데 나처럼 IQ가 130 미만이라면 직접 손으로 그려보자.

 

 

 

 

이렇게 생긴 트리였다. 이진 트리 아님.

출력은 2번 노드의 부모 ~ N번 노드의 부모가 나오면 된다.

DFS 알고리즘에 대해 떠올려보자

 

 

우리가 특정 노드를 탐색하기 위해서는 항상 그 노드의 부모 노드를 거치게 된다.

 

static void dfs(int node) {
    visited[node] = true;
    for (int v : edges.get(node)) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

 

이게 기본적인 dfs 알고리즘의 재귀함수인데

여기서 node는 각 정점을 의미하고 v는 그곳에서 파생된 자식 node를 의미한다.

그러면 부모 노드를 구하기 위해 어떻게 해야할까?

이제 다 알려줬기 때문에 여기까지 봤는데도 몰라서 답을 본다면 받아쓰기다.

잘 모르겠으면 답을 보지 말고 dfs 알고리즘을 더 공부해보자

 

 

 

 

 

 

 

 

-- > 정답

 

 

 

 

 

 

 

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

public class Main {
    static ArrayList<ArrayList<Integer>> edges = new ArrayList<>();
    static boolean[] visited;
    static int[] parents;

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

        int nodes = Integer.parseInt(br.readLine());

        for (int i=0; i<=nodes; i++) {
            edges.add(new ArrayList<>());
        }

        for (int i=0; i<nodes-1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            int node1 = Integer.parseInt(st.nextToken());
            int node2 = Integer.parseInt(st.nextToken());

            Main.edges.get(node1).add(node2);
            Main.edges.get(node2).add(node1);
        }

        visited = new boolean[nodes+1];
        parents = new int[nodes+1];

        dfs(1);
        // 루트인 1번 노드부터 시작한다.

        for (int i=2; i<parents.length; i++) {
            System.out.println(parents[i]);
            // 2번 노드부터 부모를 구하면 된다.
        }
    }

    static void dfs(int node) {
        visited[node] = true;

        for (int v : edges.get(node)) {
            if (!visited[v]) {
                dfs(v);
                parents[v]=node;
                //임의 노드 v를 만나기 위해서는 반드시 부모노드 node를 지난다.
                // 따라서 부모 노드는 반복문 안에서 만나는 node
            }
        }
    }
}