백준 - 9663. N-Queen

백트래킹 문제 중 완전 기출이기에 적어보고자 한다.

9663. N-Queen

https://www.acmicpc.net/problem/9663

 

 

문제

 

입출력

 

설명

N에 맞게 board를 생성하고 N개의 Queen을 서로 공격하지 않도록 배치하는 경우의 수를 구하면 된다.

예를 들어 아래와 같이 배치하면 성공이다.

 

접근

아래와 같이 윗 행부터 조건을 만족하는 곳들을 찾아 배치했다.

사실 if문만 잘 구현하면 된다. 나는 이 부분에서 막혀서 구현에 생각보다 오랜 시간이 걸렸다.

 

풀이 코드

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

public class Main {

    static int N;
    static int answer;
    static int[] board;

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

        N = Integer.parseInt(br.readLine());
        board = new int[N];
        Arrays.fill(board, -1);

        backTrack(0);
        System.out.print(answer);
    }

    static void backTrack(int n) {
        if (n == N) {
            answer++;
            return;
        }

        out: for (int i = 0; i < N; i++) {
            for (int j = 0; j < n; j++) {
                if (board[j] == i || Math.abs(board[j] - i) == Math.abs(j - n)) {
                    continue out;
                }
            }

            board[n] = i;
            backTrack(n + 1);
            board[n] = -1;
        }
    }

}

 

 

후기

위 코드를 제출한 결과는 아래와 같다.

시간이 6044ms가 걸렸다.

 

다른 제출한 사람들의 시간을 보니 100ms 아래인 경우가 대부분이길래 무엇이 다른지 확인해 보았다.

int[] arr = { 0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596 };

N의 값이 1 ~ 14라는 것을 알기에 위의 배열만 활용한 코드였다.

 

나는 백트래킹이라는 틀에 갇혀 이 방법을 생각하지 못했다.

다음엔 좀 더 다양한 방법을 생각하고 구현을 시작해야겠다고 반성한다.