[백준] 11725 : 트리의 부모 찾기 (JAVA/자바)

문제

BOJ 11725 : 트리의 부모 찾기 - https://www.acmicpc.net/problem/11725

풀이

문제를 딱 처음 읽고는 뭘 하라는 건지 잘 이해가 안됐는데, 그냥 연관 관계 그래프 그린 후에 부모 노드를 찾으면 된다.

root노드(=1번 노드)부터 BFS탐색으로 탐색 시 어디 노드로부터 지금 노드에 온건지 (=부모 노드의 번호가 뭔지) 저장해두고, 결과를 print하면 된다!

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    static class Node{
        int idx;
        int root;
        ArrayList<Node> adj;

        public Node(int idx) {
            this.idx = idx;
            this.root = 0;
            this.adj = new ArrayList<>();
        }
    }

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

        Node[] nodes = new Node[n + 1];
        for (int i = 1; i <= n; i++) {
            nodes[i] = new Node(i);
        }

        for (int i = 0; i < n - 1; i++) {
            String[] inputs = br.readLine().split(" ");
            int a = Integer.parseInt(inputs[0]);
            int b = Integer.parseInt(inputs[1]);

            // 양방향
            nodes[a].adj.add(nodes[b]);
            nodes[b].adj.add(nodes[a]);
        }
        
        // BFS

        boolean[] visited = new boolean[n + 1];

        Queue<Node> q = new LinkedList<>();
        nodes[1].root = -1; //root
        q.add(nodes[1]);

        while (!q.isEmpty()) {
            Node now = q.poll();

            for (Node no : now.adj) {
                if(!visited[no.idx]){ // 방문 안했으면
                    visited[no.idx] = true;
                    no.root = now.idx; // now가 부모 노드가 된다
                    q.add(no);
                }
            }
        }

        for (int i = 2; i <= n; i++) {
            System.out.println(nodes[i].root);
        }

    }
}

정리

✔ 알고리즘 분류 - 그래프 이론, 그래프 탐색, 트리, 너비 우선 탐색, 깊이 우선 탐색
✔ 난이도 - ⚪ Silver 2

🤦‍♀️ 오늘의 메모

• 트리의 구조를 다시 한번 기억할 수 있던 문제! 어렵지 않았다.

참고 사이트

딱히 없음