문제는 아래와 같다.
처음엔 문제가 무슨 말인지 이해하기도 어려웠다.
입력예시를 그리면서 위와같이 이해를 했다.
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();
}
}
}
노드를 직접 만들어서 계산하려고 했으나 시간초과...
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