(Java) 백준 11725 트리의 부모 찾기

문제 링크

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

나의 기록

✅ 알고리즘 분류 : 트리, BFS

✅ 성공 여부 : ✔

✅ 문제 난이도 : 실버2

✅ 체감 난이도 : Hard?

접근 방법

루트 노드가 1이라는 힌트가 주어지기 때문에, 2차원 배열의 인접행렬을 입력받고, 그에 따라 루트 노드에서부터 한 레벨씩 BFS로 전진하며 부모 노드를 찾으면 될 것이라 생각했다.

 

그러나 메모리 초과가 나고 마는데...

 

원인은 2차원 인접 행렬의 쓰이지 않는 수많은 메모리들.

일반적이라면 그냥 배열이 ArrayList보다 메모리 효율이 좋다고 알고 있지만, 이번만큼은 쓰이지 않는 메모리를 줄이기 위해 2차원 ArrayList를 사용하자.

 

코드

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

public class bj11725_트리의부모찾기 {

    static int N;
    static List<List<Integer>> tree;
    static int[] ans;

    public static void main(String[] args) throws IOException {
        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        tree = new ArrayList<>();
        for(int i = 0 ; i < N+1 ; i++){
            tree.add(new ArrayList<>());
        }
        ans = new int[N+1]; // ans[i] = i 노드의 부모 노드
        for(int i = 0 ; i < N-1 ; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            tree.get(a).add(b);
            tree.get(b).add(a);
        }

        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        boolean[] visit = new boolean[N+1];
        visit[1] = true;

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

            for(int now : tree.get(parent)){
                if(!visit[now]){
                    queue.add(now);
                    ans[now] = parent;
                    visit[now] = true;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 2 ; i <= N ; i++){
            sb.append(ans[i]).append("\n");
        }
        System.out.println(sb.toString());
    }
}