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

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

문제 링크

성능 요약

메모리: 72836 KB, 시간: 660 ms

분류

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

제출 일자

2024년 8월 11일 23:33:02

문제 설명

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

입력

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

출력

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

풀이

배열로 풀게 되면 메모리아웃이 발생한다.

 

간선을 받을 때 리스트로 받아야 메모리 초과 없이 문제를 해결할 수 있다.

 

푸는 법은 간단하게 모든 노드를 방문하면서 노드 방문 이전의 노드를 결과 배열에 저장시켜둔 후 출력하면 된다.

 

메모리 초과가 발생한 코드

public class Main {

    static int N, edge[][], result[];
    static boolean visited[];

    public static void main(String args[])throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        visited = new boolean[N+1];

        edge = new int[N+1][N+1];

        result = new int[N+1];
        
        for(int i = 0 ;i<N-1;i++){
            String[] re = br.readLine().split(" ");
            int a = Integer.parseInt(re[0]);
            int b = Integer.parseInt(re[1]);

            edge[a][b] = 1;
            edge[b][a] = 1;
        }

        visited[1] = true;

        dfs(0,1);

        for(int i = 2;i<=N;i++){
            bw.write(result[i] + "\n");
        }

        bw.flush();



    }

    public static void dfs(int prev, int now){
        if(now != 1){
            result[now] = prev;
        }

        for(int  i = 1 ;i<=N;i++){
            if(edge[now][i] == 1 && !visited[i]){
                visited[i] = true;
                dfs(now,i);
            }
        }
    }



}

 

테스트 케이스 통과 코드

public class Main {

    static int N, result[];
    static boolean visited[];
    static ArrayList<ArrayList<Integer>> edge = new ArrayList<>();

    public static void main(String args[])throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());

        visited = new boolean[N+1];
        result = new int[N+1];

        for(int i = 0;i<=N;i++){
            edge.add(new ArrayList<Integer>());
        }

        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());

            edge.get(a).add(b);
            edge.get(b).add(a);
        }

        visited[1] = true;

        dfs(0,1);

        for(int i = 2;i<=N;i++){
            bw.write(result[i] + "\n");
        }

        bw.flush();



    }

    public static void dfs(int prev, int now) {
        if (now != 1) {
            result[now] = prev;
        }

        while (!edge.get(now).isEmpty()) {
            Integer i = edge.get(now).get(0);
            if (!visited[i]) {
                visited[i] = true;
                dfs(now, i);
            }
            edge.get(now).remove(0);
        }

    }



}