문제
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
출력
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
테스트 케이스 Copy
입력 1
Copy
Copy
7
1 6
6 3
3 5
4 1
2 4
4 7
출력 1
Copy
4
6
1
3
1
4
입력 2
Copy
Copy
12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12
출력 2
Copy
1
1
2
3
3
4
4
5
5
6
6일반적인 트리 문제인 줄 알고 삽질을 많이 했다.
처음 접근은
트리형태로 만든 후, 그냥 parent 구하면 되지 않나 싶엇다.
처음 생각했을 때는 테스트케이스만 봐서 그냥 CONTAIN으로 포함되어있는지 아닌지 확인하면 되지 않나? 해서
1
import java.io.*;
2
import java.util.*;
3
4
public class Main {
5
public static void main(String[] args) throws IOException {
6
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
7
StringTokenizer st = new StringTokenizer(br.readLine());
8
int n = Integer.parseInt(st.nextToken());
9
Tree tree = new Tree(n);
10
for (int i = 0; i < n - 1; i++) {
11
st = new StringTokenizer(br.readLine());
12
int a = Integer.parseInt(st.nextToken());
13
int b = Integer.parseInt(st.nextToken());
14
tree.connect(a, b);
15
}
16
tree.printParent();
17
}
18
}
19
20
class Node {
21
int data;
22
int parent;
23
24
Node(int data, int parent) {
25
this.data = data;
26
this.parent = parent;
27
}
28
}
29
30
class Tree {
31
int size;
32
List<Integer> arr = new ArrayList<>();
33
List<Node> nodeList = new ArrayList<>();
34
35
Tree(int size) {
36
this.arr = new ArrayList<>(size);
37
this.size = size;
38
this.arr.add(1); }
39
40
public boolean contains(int a) { return arr.contains(a); }
41
42
public void connect(int a, int b) {
43
if (contains(a)) {
44
Node newNode = new Node(b,a);
45
arr.add(b);
46
nodeList.add(newNode);
47
48
} else if (contains(b)) {
49
Node newNode = new Node(a,b);
50
arr.add(a);
51
nodeList.add(newNode);
52
}
53
else{
54
System.out.println("Error");
55
}
56
}
57
58
public void printParent() {
59
for (int i= 2; i<= size; i ++) {
60
for (Node node: nodeList) {
61
if (node.data == i) {
62
System.out.println(node.parent);
63
}
64
}
65
}
66
}
67
68
}
하고 장렬히 전사했다.
사실 그전에도 시간 복잡도 안지켜서 시간 초과 났다. 아무 생각 없이 반복문 쓰지 맙시다..
예외가 왜있나 생각해보다가 질문 게시판을 뒤져보니
부모 지정이 되지 않은 경우에도 가능해야 한다는 답변을 얻었다.
그러면 한 라인당 간선을 다 만든다음에, 이걸 하나씩 엮어야 하지 않을끼? 라는 생각을 하게 되었다.
그래서 생각해 보다가, 그럼 우선 모든 간선들로 다 만든 다음에, 1부터 시작해서 연관되어 있던 것들을 다 하나씩 방문하면서 부모 노드를 갱신해야 하지 않을까 라는 생각을 했다.
그럼 결국 일반적인 트리 순회가 아닌, bfs로 만들어야 하지 않을까.. 라는 생각을 했다.
거기까진 생각했는데, bfs를 자바로는 첨만들어봐서..... gpt..를...
첨 짜보는데 어떡함.
static void bfs(int start) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
visited[start] = true;
while (!queue.isEmpty()) {
int current = queue.poll();
for (int next : tree[current]) {
if (!visited[next]) {
parent[next] = current;
visited[next] = true;
queue.offer(next);
}
}
}
}이게 bfs다.
Queue queue = new LinkedList<>()가 먼고 했는데
Queue는 인터페이스고, 우린 LinkedList를 만들어서 queue처럼만 쓰기로 약속해요~ 라는 소리라고 한다. Queue 인터페이스는 큐에 요소를 넣는 offer와 , 맨 앞에 꺼를 빼는 poll을 지원한다.
맨 앞에꺼, 그러니까 1을 빼서 1과 연결되어 있는 노드들의 parent를 current로 바꾼다고 생각하면 된다. visited를 true로 바꾸기 때문에 이미 했던 것들은 넘어간다.
