백준-11725번/트리의 부모 찾기(java)

 

문제 이해

 

트리를 생성하고, 각 노드의 부모를 찾는 것을 구현하면 되는 문제이다.

 

이 문제는 시간초과 때문에 여러번 실패했다.

 

하지만 리스트로 트리를 구현하였더니 트리의 노드 삽입 및 순회 속도가 간단해져서 정답으로 인정 됐다.

 

문제 풀이

 

시간초과가 발생한 코드

import java.util.Scanner;

public class Problem11725 {
    static Node head = new Node(1,null,null);
    static boolean check;
    static boolean[] visit;
    static int[] parent;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        scanner.nextLine();
        visit=new boolean[N+1];
        parent = new int[N+1];

        for(int i=0; i<N-1; i++){
            int parent = scanner.nextInt();
            int son = scanner.nextInt();
            check=false;
            insertNode(head,parent,son);
            if(check==false){
                insertNode(head,son,parent);
            }
        }
        dfs(head);

        for(int i=2; i<=N; i++){
            System.out.println(parent[i]);
        }

    }

    public static class Node{
        private int data;
        private Node left;
        private Node right;

        Node(int data, Node left, Node right){
            this.data = data;
            this.left=left;
            this.right = right;
        }

    }
    public static void insertNode(Node tmp, int root, int data) {
        if (tmp == null) {
            return;
        }
        if (tmp.data == root) {
            if (tmp.left == null) {
                tmp.left = new Node(data, null, null);
                check=true;
            } else if (tmp.right == null) {
                tmp.right = new Node(data, null, null);
                check=true;
            }
        } else {
            insertNode(tmp.left, root, data);
            insertNode(tmp.right, root, data);
        }
    }

    public static void dfs(Node node){
        visit[node.data]=true;

        if(node.left!=null && !visit[node.left.data]){
            parent[node.left.data]=node.data;
            dfs(node.left);
        }
        if(node.right!=null && !visit[node.right.data]){
            parent[node.right.data]=node.data;
            dfs(node.right);
        }

    }
}

 

 

ArrayList로 구현한 트리

import java.util.ArrayList;
import java.util.Scanner;
import java.util.List;

public class Problem11725_2 {
    static List<Integer>[] tree;
    static int[] parent;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        scanner.nextLine();

        tree = new ArrayList[N + 1];
        parent = new int[N + 1];
        visited = new boolean[N + 1];

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

        for (int i = 0; i < N - 1; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            scanner.nextLine();

            tree[a].add(b);
            tree[b].add(a);
        }

        dfs(1);

        for (int i = 2; i <= N; i++) {
            System.out.println(parent[i]);
        }
    }

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

        for (int child : tree[node]) {
            if (!visited[child]) {
                parent[child] = node;
                dfs(child);
            }
        }
    }
}

 

트리를 리스트로 구현하면 노드 삽입이 매우 간단해지고 dfs도 트리 순회가 간단해져서 매우 빨라진다.

 

주의할 점 : 간선을 입력받아 꼭 양방향으로 연결해야 한다.