BOJ 11725 - 트리의 부모 찾기

문제

문제 풀기

접근

이 문제는 1의 값을 가지는 루트노드가 고정되어있고, 연결된 두 정점들이 세트 단위의 입력으로 주어진다. 두 정점간 어떤 노드가 부모인지 주어지지 않기 때문에 트리를 잘 만들어내는 것이 이 문제의 핵심이다.

1. 트리를 구현하기 위한 자료구조로 연결리스트 배열을 사용한다.
2. 노드의 부모를 기록하기 위한 parent배열을 사용한다. (루트노드는 부모가 없으므로 자기자신인 1을 넣는다.)
3. 일단 부모를 알 수 없기 때문에 양방향으로 두 노드를 연결을 시킨다.(두 노드에 자식들을 관리하는 연결리스트들에 서로를 추가한다.)
4. 입력이 끝났다면 bfs로 루트노드부터 탐색한다.

   1. 자식 노드를 queue에 넣을 때 본인이 부모이므로 parent의 값을 현재 노드의 값으로 넣는다.
   2. 만약 자식 노드의 부모가 있다면(3번에서 양방향으로 노드를 연결시켜줬기 때문에 이미 부모를 찾은 노드를 중복으로 또 마주할 수 있음) 해당 과정 생략

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        // 입력
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(in.readLine());
        int parent[] = new int[N+1];
        ArrayList<Integer> nodes[] = new ArrayList[N+1];
        for(int i = 1 ; i <= N ; i++ ) nodes[i] = new ArrayList<>();
        for(int i = 0 ; i < N-1 ; i++){
            st = new  StringTokenizer(in.readLine(), " ");
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            nodes[from].add(to);
            nodes[to].add(from);
        }

        // 처리 - bfs 탐색하며 부모를 찾아간다.
        parent[1] = 1; //root 노드라서 부모를 자기 자신으로 한다.
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(1);

        while (!queue.isEmpty()){
            int directParent = queue.poll();
            for(int child : nodes[directParent]){
                if( parent[child] != 0 ) continue; // 부모를 찾은 경우 건너뜀
                parent[child] = directParent;
                queue.add(child);
            }
        }
        for(int i = 2 ; i <= N ; i++){
            sb.append(parent[i]);
            sb.append("\n");
        }
        System.out.println(sb);
    }
}