내 코드
public class Test17 {
public void main() {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
int n = Integer.parseInt(br.readLine());
// 트리 만들기
ArrayList<ArrayList<Integer>> tree = new ArrayList<>();
for (int i = 0; i <= n; i++) {
tree.add(new ArrayList<>());
}
for (int i = 0; i < n - 1; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int l = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
tree.get(l).add(r);
tree.get(r).add(l);
}
// 부모 찾기 BFS
int[] p = new int[n + 1];
Queue<Integer> q = new LinkedList<>();
q.offer(1);
while (! q.isEmpty()) {
int now = q.poll();
ArrayList<Integer> child = tree.get(now);
for (int i = 0; i < child.size(); i++) {
int cur = child.get(i);
if (p[cur] != 0) continue;
p[cur] = now;
q.offer(cur);
}
}
for (int i = 2; i < p.length; i++) {
System.out.println(p[i]);
}
} catch (Exception e) {
System.out.println("err 😭");
e.printStackTrace();
}
}다른 사람 코드 1
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[] parent = new int[n + 1];
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
// list 초기화
for (int i = 0; i <= n; i++) {
list.add(new ArrayList<>());
}
// 데이터(노드) 삽입
for (int i = 1; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int node1 = Integer.parseInt(st.nextToken());
int node2 = Integer.parseInt(st.nextToken());
list.get(node1).add(node2);
list.get(node2).add(node1);
}
// 부모 찾기 : Q 이용
// 각 노드 큐에 저장
Queue<Integer> q = new LinkedList<>();
q.offer(1); // root 입력
while (!q.isEmpty()) {
int now = q.poll();
for (int child: list.get(now)) {
if (parent[child] != 0) continue;
parent[child] = now;
q.offer(child);
}
}
// 부모 출력
for (int i = 2; i <= n; i++) {
System.out.println(parent[i]);
}다른 사람 코드2
import java.io.*;
import java.util.*;
public class Main {
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(n);
for (int i = 1; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
tree.addEdge(a, b);
}
tree.bfs(1);
tree.printParents();
}
}
class Tree {
private ArrayList<ArrayList<Integer>> list;
private int[] parents;
private int size;
public Tree(int n) {
size = n;
list = new ArrayList<>();
parents = new int[n + 1];
for (int i = 0; i <= n + 1; i++) {
list.add(new ArrayList<>());
}
}
public void addEdge(int a, int b) {
list.get(a).add(b);
list.get(b).add(a);
}
public void bfs(int start) {
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[size + 1];
visited[start] = true;
queue.add(start);
while (!queue.isEmpty()) {
int currentNode = queue.poll();
for (int nextNode : list.get(currentNode)) {
if (!visited[nextNode]) {
visited[nextNode] = true;
parents[nextNode] = currentNode;
queue.add(nextNode);
}
}
}
}
public void printParents() {
for (int i = 2; i <= size; i++) {
System.out.println(parents[i]);
}
}
}트리는 그래프의 한 종류로서 특정한 제약 조건을 충족하는 계층적인 구조를 가지고 있다.
루트 노드가 있으면 트리, 루트 노드가 없으면 그래프라고 볼 수도 있다.
어려웡 🙄
트리와 그래프. BFS, DFS
좀 오래 봐야할 느낌이다 🤔
BFS 너비 우선 탐색 알고리즘
시작 노드로부터 가장 가까운 노드 들을 먼저 탐색 한 후,
더 멀리 떨어져 있는 노드들을 차례대로 탐색하는 방식이다.
자료구조인 큐를 활용하며 , FIFO 원칙을 따른다.
BFS 알고리즘 수행 과정
- 시작 노드를 큐에 넣고, 방문 처리를 한다.
- 큐에서 노드를 꺼내어,
그 노드의 인접 노드들 중 아직 방문하지 않은 노드를 모두 큐에 넣고 방문 처리를 한다. - 큐가 빌때까지 2번을 반복한다.
BFS 알고리즘의 특징
- 시작 노드에서 다른 노드까지의 최단 경로를 찾을 수 있다.
각 단계마다 가장 가까운 노드부터 탐색하기 때문이다. - 큐를 사용하여 탐색 순서를 관리한다.
이것은 DFS 알고리즘과 구분되는 점이다. DFS는 스택이나 재귀를 사용! - 그래프의 모든 노드를 방문할 수 있다.
이것은 완전 탐색 알고리즘으로 사용될수 있음을 뜻한다.
다시 풀어본 날 : 23.03.30 _ 04.01 _ 04.08 _ 04.09
실패 : 23.03.31 _ 04.02🤯
아오 어려웡 😭
04.08 _ 몇번 더 풀어봐야됨 😔
04.09 _ 드디어 막힘없이 한번에 풀긴 풀었는데 아직도 어렵다;; 이 문제는 익숙해질때까지 풀어보는걸로~~
Hello velog!