백준 9663번 메모리초과

SuYeong·2023년 12월 9일

안녕하세요.

오늘은 백준 9663번을 자바로 풀이하면서 발생했던 메모리 초과 문제의 원인과 해결책을 정리해보겠습니다.
(문제 링크 : https://www.acmicpc.net/problem/9663)

결론부터 말씀드리면,
메모리초과 문제의 원인은 객체를 많이 만드는 코드로 인한 힙 메모리 부족이었고,
해결책은 객체 생성을 적게하거나 하지 않는 방향으로의 코드 수정입니다.

아래는 메모리초과 코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int input = Integer.parseInt(br.readLine());
        Solution solution = new Solution(input);
        solution.dfs(0);
        solution.printResult();
    }

    static class Solution {

        private final int panSize;

        private final List<Pair> list = new ArrayList<>();
        private int result = 0;

        public Solution(int panSize) {
            this.panSize = panSize;
        }

        public void dfs(int depth) {

            if (depth == panSize) { // 모든 행에 퀸을 놓은 상태라면
                result++;
                return;
            }

            for (int nowCol = 0; nowCol < panSize; nowCol++) {
                if (can(depth, nowCol)) { // depth행, nowCol열에 queen을 놓을 수 있는지 확인
                    list.add(new Pair(depth, nowCol)); // 문제가 되는 부분!!
                    dfs(depth + 1); // depth + 1 행에 queen을 놓는 방법 탐색
                    list.remove(list.size() - 1); // depth 행에 두었던 queen 제거
                }
            }
        }

        public boolean can(int depth, int col) {
            for (Pair coordinate : list) {
                int rowDifference = depth - coordinate.getRow();
                if (col == coordinate.col || // 같은 열에 있다면
                        (col == coordinate.getCol() + rowDifference) || // 우하 방향 겹치는지 확인
                        (col == coordinate.getCol() - rowDifference)) { // 좌하 방향 겹치는지 확인
                    return false;
                }
            }
            return true;
        }

        public void printResult() {
            System.out.println(result);
        }
    }

    static class Pair {
        private final int row;
        private final int col;

        public Pair(int row, int col) {
            this.row = row;
            this.col = col;
        }

        public int getRow() {
            return row;
        }

        public int getCol() {
            return col;
        }

        @Override
        public String toString() {
            return "{" +
                    row +
                    ',' +
                    col +
                    '}';
        }
    }
}

위 코드에서 list.add(new Pair(depth, nowCol)) 이 문제가 되는 부분이었습니다.
새로운 칸을 방문할 때마다 Pair 객체를 만들기 때문에 힙 메모리 사용량이 급격하게 증가했습니다.

아래와 같이 메모리 사용량이 350MB까지 증가하고 감소하기를 반복했습니다.
(9:30:45에 그래프 모양이 약간 이상한 이유는 해당 부분에서 heap dump를 떴기 때문입니다)

아래는 Heap dump를 추출한 시기에 Heap을 차지하고 있는 클래스 인스턴스 갯수와 용량입니다.

Heap의 98.5%를 Pair 클래스의 인스턴스가 차지하고 있음을 확인할 수 있습니다.

인스턴스를 계속 생성하는 것이 문제가 됨을 확인했으니, 코드를 아래와 같이 개선해보았습니다.

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int input = Integer.parseInt(br.readLine());
        Solution solution = new Solution(input);
        solution.dfs(0);
        solution.printResult();
    }

    static class Solution {

        private final int panSize;

        private final int[] arr;
        private int result = 0;

        public Solution(int panSize) {
            this.panSize = panSize;
            this.arr = new int[panSize];
        }

        public void dfs(int depth) {

            if (depth == panSize) {
                result++;
                return;
            }

            for (int nowCol = 0; nowCol < panSize; nowCol++) {
                if (can(depth, nowCol)) {
                    arr[depth] = nowCol;
                    dfs(depth + 1);
                }
            } 
        }

        public boolean can(int depth, int col) {
            for (int i = 0; i < depth; i++) {
                int rowDifference = depth - i;
                if(col == arr[i] ||
                        (col == arr[i] + rowDifference) ||
                        (col == arr[i] - rowDifference)) {
                    return false;
                }
            }
            return true;
        }

        public void printResult() {
            System.out.println(result);
        }
    }

}