[백준/Silver II] 트리의 부모 찾기 - 11725

[Silver II] 트리의 부모 찾기 - 11725

문제 링크

성능 요약

메모리: 139276 KB, 시간: 1184 ms

분류

그래프 이론, 그래프 탐색, 트리, 너비 우선 탐색, 깊이 우선 탐색

제출 일자

2024년 11월 1일 13:14:50

문제 설명

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

제출코드

//https://www.acmicpc.net/problem/11725
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());
        HashMap<Integer, ArrayList<Integer>> tree = new HashMap<>();

        ArrayList<Integer> temp;
        for(int i = 1; i < n; i++){
            int[] nodes = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            // 간선 표시
            temp = tree.getOrDefault(nodes[0] , new ArrayList<Integer>());
            temp.add(nodes[1]);
            tree.put(nodes[0], temp);
            temp = tree.getOrDefault(nodes[1] , new ArrayList<Integer>());
            temp.add(nodes[0]);
            tree.put(nodes[1], temp);
        }


        // tree 탐색하면서 map에 부모 노드담기
        HashMap<Integer, Integer> map = new HashMap<>(); // key:노드, value:key의 부모노드
        Queue<Integer> queue = new LinkedList<>(); // 탐색 경로 큐
        // 트리의 루트 담아주기 (1로 지정됨)
        map.put(1, 0);
        queue.add(1);
        while(!queue.isEmpty()){
            int current = queue.poll();
            for(Integer node: tree.get(current)){
                if(!map.containsKey(node)){ // 간선이 이어져있고 탐색한 적 없는 노드면
                    queue.add(node); // node를 다음 탐색 경로에 추가.
                    map.put(node, current); // map에 node의 부모노드가 current임을 담아줌.
                }
            }
        }

        // 2~n까지 map을 순회하면서 부모노드 출력
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i = 2 ; i <= n; i++){
            bw.write(map.get(i)+"\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}