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

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

11725번: 트리의 부모 찾기

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static StringTokenizer st;
    static ArrayList<Integer>[] tree;
    static boolean[] visit;
    static int[] parents;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(br.readLine());
        tree = new ArrayList[N + 1];
        parents = new int[N + 1];
        visit = new boolean[N + 1];

        for (int i = 1; i <= N; i++) {
            tree[i] = new ArrayList<>();
        }
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
            tree[n1].add(n2);
            tree[n2].add(n1);
        }

        search(1);
        for (int i = 2; i <= N; i++) {
            sb.append(parents[i]).append("\n");
        }
        System.out.println(sb);
    }

    private static void search(int root) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        visit[1] = true;
        while (!queue.isEmpty()) {
            int parent = queue.poll();
            for (int child : tree[parent]) {
                if(visit[child]) continue;
                parents[child] = parent;
                queue.add(child);
                visit[child] = true;
            }
        }
    }
}

💡 그래프, BFS

- 처음 시도 : 부모 노드를 배열에 기록하는 배열을 생성한 뒤, 주어진 2개의 노드를 토대로 값이(부모 노드 번호) 0인 노드에 일치하지 않는 노드를 할당하는 방식으로 진행함

public class Main_11725 {
    static int N;
    static StringTokenizer st;
    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        parent = new int[N + 1]; //idx = 자식노드, value = 부모노드
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
            setChildNode(n1, n2);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 2; i <= N; i++) {
            sb.append(parent[i]).append("\n");
        }
        System.out.println(sb);
    }

    private static void setChildNode(int n1, int n2) {
        for (int i = 2; i <= N; i++) {
            if(n1 == i && parent[n1] == 0) {
                parent[n1] = n2;
                return;
            }
            if(n2 == i && parent[n2] == 0) {
                parent[n2] = n1;
                return;
            }
        }
    }
}

 => 뒤늦게 루트노드에 연결되는 작은 트리의 경우 순서가 바뀜 : 오류

풀이

• 그래프처럼 ArrayList의 배열을 만들어 부모 노드에 대해서 자식노드들을 추가하는 방식으로 생성
  
  • 들어온 n1, n2에 대해 일단 양 방향으로 추가를 하고, 나중에 출력할 때 지워나가는 방식
• 탐색에서 루트노드 1부터 자식 노드로 BFS 방식으로 탐색해 나감
  • 중복 방문을 방지하기 위해 visit 배열을 따로 만들어 관리함