문제 접근

전형적인 백트래킹 문제로, 학교 알고리즘 시간에 배운게 기억나는 문제였다. 이 문제는 결국 모든 행에 하나씩 배치를 해봐야해서 만약 행개수가 n이라면, n^n을 모두 확인해봐야 한다. 하지만, 문제에서 n은 최대 14이고, 시간 복잡도는 10초라고 했다. 따라서 10억초 안에 해결해야한다.
즉, 14^14로는 절대 풀지 못한다. 유망성 검사로, 이번에 배치하려는 위치가 지금까지 배치했던 말들에게 먹히지 않는지를 확인해야한다.

문제 풀이

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

class Main {
    static int N;
    static int result = 0;
    static int[] rs = new int[14];
    static int[] cs = new int[14];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        dfs(0);
        System.out.println(result);
    }

    private static void dfs(int r) {
        if (r == N) {
            result++;
            return;
        }

        for (int c = 0; c < N; c++) {
            if (!isPromise(r, c)) continue;
            rs[r] = r;
            cs[r] = c;
            dfs(r + 1);
            rs[r] = 0;
            cs[r] = 0;
        }
    }

    private static boolean isPromise(int r, int c) {
        for (int t = 0; t < r; t++) {
            int i = rs[t];
            int j = cs[t];
            if (i == r || j == c) return false;
            if (Math.abs(r - i) == Math.abs(c - j)) return false;
        }
        return true;
    }
}

여담

• 처음에 Point라는 클래스를 만들어서, 말들의 위치를 저장하는 ArrayList를 만들어서 관리했다. 그랬더니 메모리 초과가 났다... 자바 문제를 풀 때는 우리가 직접 메모리 해제를 못해주기 때문에(사용자 정의 JVM을 작성하지 않는한... ) 클래스 쓸때 각별히 주의해야할 것 같다.