Algorithm/Baekjoon_acmicpc
백준 11725 - 트리의부모찾기,시뮬레이션,우선순위큐, 그리디,알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, Leetcode, search, greedy,acmicpc,bfs,dfs, priority queue
Ginjoe
2021. 5. 11. 01:54
// Process
// 1. Input n, edges
// 2. Make node lists with adjacents
// 3. Make stack, and put first root node
// 4. Iterate while stack is not empty
// 4.1. Iterate adjacents
// 4.1.1. Set parent number, if this adjacent is not visited yet
// 5. Print all parent numbers from 2 to end
// 6. Finish
import java.io.*;
import java.util.*;
class FindParentTree {
public static void main(String[] args) throws IOException {
// 1, 2.
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Node[] nodes = new Node[n];
for (int i = 0; i < n; ++i) {
nodes[i] = new Node(i);
}
for (int i = 0; i < n-1; ++i) {
String[] temp = br.readLine().split(" ");
nodes[Integer.parseInt(temp[0])-1].adjacents.add(nodes[Integer.parseInt(temp[1])-1]);
nodes[Integer.parseInt(temp[1])-1].adjacents.add(nodes[Integer.parseInt(temp[0])-1]);
}
// 3.
int[] parentNumbers = new int[n];
Stack<Node> stack = new Stack<>();
stack.push(nodes[0]);
// 4.
while (stack.size() > 0) {
Node popNode = stack.pop();
for (int i = 0; i < popNode.adjacents.size(); ++i) {
if (!popNode.adjacents.get(i).isVisited) {
stack.push(popNode.adjacents.get(i));
popNode.adjacents.get(i).isVisited = true;
parentNumbers[popNode.adjacents.get(i).value] = popNode.value;
}
}
}
// 5.
for (int i = 1; i < parentNumbers.length; ++i) {
System.out.println(parentNumbers[i]+1);
}
}
static class Node {
int value;
boolean isVisited;
List<Node> adjacents = new ArrayList<>();
public Node(int value) {
this.value = value;
this.isVisited = false;
}
}
}