[백준] 11725번 - 트리의 부모 찾기 [Java]

https://www.acmicpc.net/problem/11725

 

[백준] 11725번 - 트리의 부모 찾기 [Java]

[백준] 11725번 - 트리의 부모 찾기 [Java]

---

1.  아이디어

 

각 노드의 부모를 저장하는 p 배열을 활용한 BFS, DFS로 해결할 수 있다.

---

2. 문제풀이

 

BFS, DFS 모두 인접 리스트에서 인접 노드를 탐색하도록 구현이 되는데 이때 트리의 루트부터 탐색 시 다음 노드가 현재 노드의 자식이 됨을 활용했다. p 배열에서 인덱스 번호를 노드 번호, 값을 부모 노드의 번호를 저장하도록 한 후 출력하는 방식으로 구현했다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main_BFS {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            adj.get(u).add(v);
            adj.get(v).add(u);
        }

        int[] p = bfs(N, adj);
        for (int i = 2; i <= N; i++) {
            sb.append(p[i]).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }

    private static int[] bfs(int N, List<List<Integer>> adj) {
        Queue<Integer> q = new ArrayDeque<>();
        q.add(1);

        boolean[] visited = new boolean[1 + N];
        visited[1] = true;

        int[] p = new int[1 + N];

        while (!q.isEmpty()) {
            int node = q.remove();

            for (int next : adj.get(node)) {
                if (visited[next]) continue;

                q.add(next);
                visited[next] = true;
                p[next] = node;
            }
        }

        return p;
    }

}

import java.io.*;
import java.util.*;

public class Main_DFS {

    private static final List<List<Integer>> adj = new ArrayList<>();
    private static boolean[] visited;
    private static int[] p;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i <= N; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            adj.get(u).add(v);
            adj.get(v).add(u);
        }

        visited = new boolean[1 + N];
        p = new int[1 + N];

        dfs(1);

        for (int i = 2; i <= N; i++) {
            sb.append(p[i]).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }

    private static void dfs(int node) {
        visited[node] = true;

        for (int next : adj.get(node)) {
            if (visited[next]) continue;

            p[next] = node;
            dfs(next);
        }
    }

}

---

4. 후기

 

- BFS

- DFS