[백준 11725번] 트리의 부모찾기(자바)

과제를 해결하기전에 풀어보라고 나온 힌트문제...

어디를 어떻게 풀어나가야할지 감도 안잡히고 고민하다가 결국

시간낭비하지말고 다른사람의 코드를 해체해서 배워보기로했다.

 

여기서 풀이를 참조해봤는데 

BFS를 이용하여 문제를 풀어나갔다.

https://velog.io/@doxxx93/boj-11725

[백준] 11725번 : 트리의 부모 찾기 - JAVA [자바]

 

 

 

위에 코드에서  권장하지 않는

StringTokenizer를   String[] node = br.readLine().split(" ");로 
변경하였다.
코드를 해체해서 배운다고는 했으나,
나에겐 너무나도 상위단계같은 느낌이 난다..
아직 더 쉬운 구현들조차 어려운 것 같아서 혼자 차근차근해 볼 생각이다.



BFS


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());

int[] parent = new int[n + 1];

ArrayList<Integer>[] adj = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
adj[i] = new ArrayList<>();
}

boolean[] visited = new boolean[n + 1];

for (int i = 1; i < n; i++) {

String[] node = br.readLine().split(" ");

int a = Integer.parseInt(node[0]);
int b = Integer.parseInt(node[1]);

adj[a].add(b);
adj[b].add(a);
}

Queue<Integer> queue = new LinkedList<>();

queue.add(1);
visited[1] = true;

while (!queue.isEmpty()) {
int cur = queue.poll();

for (int next : adj[cur]) {
if (visited[next]) {
continue;
}

visited[next] = true;
queue.add(next);

parent[next] = cur;
}
}

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








DFS

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());

int[] parent = new int[n + 1];
ArrayList<Integer>[] adj = new ArrayList[n + 1];

for (int i = 1; i <= n; i++) {
adj[i] = new ArrayList<>();
}

for (int i = 1; i < n; i++) {
String[] node = br.readLine().split(" ");

int a = Integer.parseInt(node[0]);
int b = Integer.parseInt(node[1]);

adj[a].add(b);
adj[b].add(a);
}

dfs(1, adj, parent);

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

private static void dfs(int cur, ArrayList<Integer>[] adj, int[] parent) {

for (int next : adj[cur]) {

if (parent[next] == 0) {
parent[next] = cur;
dfs(next, adj, parent);
}

}
}
}