백준 11725

문제는 아래와 같다.

문제이해

처음엔 문제가 무슨 말인지 이해하기도 어려웠다.

입력예시를 그리면서 위와같이 이해를 했다.

트라이1

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;

public class Solution5 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Tree tree = new Tree();
        for (int i = 0; i < n - 1; i++) {
            String[] input = br.readLine().split(" ");
            int data1 = Integer.parseInt(input[0]);
            int data2 = Integer.parseInt(input[1]);
            tree.insert(data1, data2);
        }
        tree.print();
        br.close();
    }
}

class Node implements Comparable<Node>{
    int data;
    Node parent;
    Node (){}
    Node (int data, Node parent){
        this.data = data;
        this.parent = parent;
    }


    @Override
    public int compareTo(Node o) {
        if (this.data > o.data){
            return 0;
        } else {
            return -1;
        }
    }
}
class Tree {
    Node root = new Node(1, null);
    ArrayList<Node> arrList = new ArrayList<>();
    Tree(){
        this.arrList.add(this.root);
    }
    public void insert (int data1, int data2){
        for (int i = 0; i < arrList.size(); i++) {
            if (data1 == arrList.get(i).data) {
                arrList.add(new Node(data2, arrList.get(i)));
                break;
            } else if(data2 == arrList.get(i).data) {
                arrList.add(new Node(data1, arrList.get(i)));
                break;
            }
        }
    }

    public void print() throws IOException{
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Collections.sort(arrList);
        for (int i = 1; i < arrList.size(); i++) {
            bw.write(arrList.get(i).parent.data + "\n");
            bw.close();
        }
    }
}

노드를 직접 만들어서 계산하려고 했으나 시간초과...

트라이2

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Solution5_1 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        ArrayList<int[]> arrList = new ArrayList<>();
        arrList.add(new int[]{1,});
        LinkedList<Integer> childList = new LinkedList<>();
        childList.add(1);

        for (int i = 0; i < n - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int[] node = new int[2];
            node[0] = Integer.parseInt(st.nextToken());
            node[1] = Integer.parseInt(st.nextToken());
            if (childList.contains(node[0])){
                int tmp = node[0];
                node[0] = node[1];
                node[1] = tmp;
            }
            arrList.add(node);
            childList.add(node[0]);
        }

        int[][] sorted = new int[n][2];
        for (int i = 0; i < arrList.size(); i++) {
            sorted[arrList.get(i)[0]-1] = arrList.get(i);
        }

        for (int i = 1; i < sorted.length; i++) {
            bw.write(sorted[i][1] + "\n");
        }
        bw.close();
        br.close();
    }
}

최대한 이중 반복문 등을 제외하려고 풀려고 했으나 이것도 시간초과..

최종(구글신의 도움)

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 Solution5_2 {

    public static int[] parents;
    public static ArrayList<Integer>[] list;
    public static int N;
    public static boolean[] isVisit;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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<>();
        }

        for (int i = 0; i < N - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list[a].add(b);
            list[b].add(a);
               
        dfs(1);

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

    public static void dfs(int index) {
        isVisit[index] = true; 
        for (int i : list[index]) {
            if (!isVisit[i]) { 
                parents[i] = index;
                dfs(i);
                
            }
        }
    }
}

dfs 재귀함수로 푸셨다.. 구글링 만세.. 다음에 내가 한거보다 이 코드가 연산이 가벼운 이유를 좀 살펴봐야 할 것 같다. ㅠㅠ
참고
https://codesign.tistory.com/122