9663번. N-Queen

 

아이디어

N-Queen 문제는 대표적인 백트래킹 문제다. 

퀸의 공격 범위는 같은 행, 열, 대각선이므로 이를 고려해서 문제를 해결하면 된다.

 

1 ~ i-1번 퀸이 놓인 위치를 저장해놓고 i번 퀸을 놓을 차례 때 이전에 놓인 퀸들의 위치에 기반해서 같은 행이나, 열, 대각선이 아닌 곳이 존재하면 해당 위치에 i번 퀸을 놓고 다음 차례로 가는 것이다.

 

만약 존재하지 않는다면 i - 1 번째 퀸의 위치를 조정할 필요가 있는 것이므로 가능한 후보 중 다른 위치에 옮긴 후에 다시 탐색을 이어가면 된다.

 

2차원 배열을 만들어서 문제를 해결해도 되지만 이 문제의 경우 index 를 '열'로 간주하고 해당 index 에 '행'을 저장하는 1차원 배열만으로도 충분히 퀸의 위치를 표현할 수 있으므로 메모리 낭비를 줄이기 위해 1차원 배열을 사용했다.

 

 

풀이코드

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

public class Main {

    static int N;
    static List<Integer> putRows = new ArrayList<>();
    static int result = 0;

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

        N = Integer.parseInt(br.readLine());
        putQueen(0);
        System.out.println(result);
    }

    public static void putQueen(int col) {
        if (col == N) {
            result++;
            return;
        }

        for (int row = 0; row < N; row++) {
            if (isPossible(row, col)) {
                putRows.add(row);
                putQueen(col + 1);
                putRows.remove(putRows.size() - 1);
            }
        }
    }

    public static boolean isPossible(int row, int col) {
        int len = putRows.size();
        for (int i = 0; i < len; i++) {
            int putRow = putRows.get(i);
            if (putRow == row || putRow + (col - i) == row || putRow - (col - i) == row) return false;
        }

        return true;
    }
}