BOJ) 트리의 부모 찾기 (11725, JAVA)

트리의 부모 찾기

11725번: 트리의 부모 찾기

풀이

 

처음에는 1차원 배열로 문제를 풀려고 하다가, 연결 관계에서 부모 관계를 파악하기 힘들다는 문제를 발견했다.

그래서 BFS로 풀어야겠다는 마음을 먹었다.

 

우선 map을 저장해줘야 하는데, 배열을 사용할 수 없다. (최악의 경우 100,000 by 100,000가 된다)

그래서, ArrayList 배열에 map의 관계를 저장했다. (레코드 조회만 필요하기 때문에 ArrayList가 더 적절하다고 판단했다.)

 

맵이 저장된 다음에는 Queue를 통해 부모를 짝지어주었다.

root인 1부터 시작하면서 1과 연결되어있는 노드들을 queue에 넣어주면서 parent를 설정해주었다.

이후, 2부터 n까지 조회하면서 부모 노드를 StringBuffer에 넣어두고 출력해줬다. (속도와 메모리 성능)

 

 

코드

 

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 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        ArrayList<Integer>[] map = inItMap(n);

        for(int i=1; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int left =Integer.parseInt(st.nextToken());
            int right =Integer.parseInt(st.nextToken());
            map[left].add(right);
            map[right].add(left);
        }
        br.close();
        solution(n, map);
    }

    private static void solution(int n, ArrayList<Integer>[] map) {
        final int root = 1;
        int[] parents = new int[n+1];
        Queue<Integer> queue = new LinkedList<>();

        parents[root] = root;
        queue.offer(root);

        while(!queue.isEmpty()) {
            int origin = queue.poll();
            for(int child : map[origin]) {
                if(parents[child] ==0) {
                    parents[child] = origin;
                    queue.offer(child);
                }
            }
        }

        final String newLine = "\n";
        StringBuffer sb = new StringBuffer();

        for(int i=2; i<=n; i++) {
            sb.append(parents[i]).append(newLine);
        }
        System.out.println(sb.toString());
    }
    private static ArrayList<Integer>[] inItMap(int n) {
        ArrayList<Integer>[] result = new ArrayList[n+1];
        for(int i=1; i<=n; i++) result[i] = new ArrayList<>();
        return result;
    }
}