인접 행렬, 인접 리스트

백준 트리의 부모 문제를 푸는데 계속 메모리 초과 문제가 발생했다.
https://www.acmicpc.net/problem/11725

dfs의 스택오버플로우로 인한 문제인가 싶어서 bfs로 전환했지만 문제는 해결되지 않았다. 검색해서 찾아보니 인접행렬 사용으로 인한 메모리 초과문제였다.

인접행렬과 인접리스트는 어떤 차이가 있어서 문제가 발생하는걸까?

인접행렬

인접행렬은 다음과 같이 인덱스 개수만큼 행과 열이 생긴다.

인접리스트

인접리스트는 다음과 같이 한 정점에 대하여 관계가 있는 정점만을 저장해 더 효율적인 관계 표현이 가능하다.

위 문제는 n이 10,000까지 커질 수 있기 때문에 이를 이차원배열로 만든다면 엄청난 메모리를 사용하게 된다.

코드를 수정해보자

초기 코드

package org.example;

import java.io.*;
import java.util.*;

public class Main {
    int n;
    int[] parents;
    boolean[] visit;
    int[][] map;

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;

    void bfs(int v){
        Queue<Integer> q = new LinkedList<>();
        q.offer(v);
        visit[v] = true;

        while(!q.isEmpty()){
            int size = q.size();

            for(int i=0;i<size;i++){
                int parent = q.poll();

                for(int j=1;j<=n;j++){
                    if(!visit[j]&&map[parent][j]==1){
                        parents[j] = parent;
                        visit[j] = true;
                        q.offer(j);
                    }
                }
            }
        }
    }

    void solution() throws Exception {
        n = Integer.parseInt(br.readLine());
        parents = new int[n+1];
        visit = new boolean[n+1];
        map = new int[n+1][n+1];

        for(int i=0;i<n-1;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            map[a][b] = 1;
            map[b][a] = 1;
        }

        bfs(1);

        for(int i=2;i<=n;i++){
            System.out.println(parents[i]);
        }
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

수정된 코드

package org.example;

import java.io.*;
import java.util.*;

public class Main {
    int n;
    int[] parents;
    boolean[] visit;
    ArrayList<Integer>[] map;

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;

    void bfs(int v){
        Queue<Integer> q = new LinkedList<>();
        q.offer(v);
        visit[v] = true;

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

            for(int m:map[parent]){
                if(!visit[m]){
                    visit[m] = true;
                    parents[m] = parent;
                    q.offer(m);
                }
            }
        }
    }

    void solution() throws Exception {
        n = Integer.parseInt(br.readLine());
        parents = new int[n+1];
        visit = new boolean[n+1];
        map = new ArrayList[n+1];

        for(int i=1;i<=n;i++){
            map[i] = new ArrayList<>();
        }

        for(int i=0;i<n-1;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            map[a].add(b);
            map[b].add(a);
        }

        bfs(1);

        for(int i=2;i<=n;i++){
            System.out.println(parents[i]);
        }
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

여담으로 위 수정된 코드에는 Queue를 LinkedList로 사용했지만 ArrayDeque<Integer> q = new ArrayDeque<>();를 사용하는 것이 더 경량이라고 한다. 나중에 문제가 되거나 생각나면 써봐도 좋을듯하다.