[백준/Java] 9663 N-Queen

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

문제 요약

N x N 체스판 위에 N개의 퀸을 서로 공격할 수 없게 놓아야 한다.
N이 주어질 때, 퀸을 놓는 방법의 수를 구하자.
이때 N은 1 이상, 15 이하이다.

---

문제 접근

N이 최대 15니까 전체 체스판은 최대 15*15이다.
최대의 N이 작고, 시간제한도 상당히 여유롭기 때문에, 조건을 만족하는 모든 경우를 훑는 완전탐색을 사용해도 된다.

이 문제는 다음과 같은 방법으로 해결할 수 있다.

1. 1차원 배열 arr[]을 생성한다: 한 줄에는 퀸 하나만 배치 가능하기 때문이다.
   -> arr[row]=column 의 꼴로 모든 퀸의 위치를 저장할 수 있다.
2. 다음 줄에 퀸을 놓을 때 고려해야 할 점
   a. 이미 퀸이 있는 column에는 퀸을 놓을 수 없다.
   b. 이미 있는 퀸의 대각선에는 퀸을 놓을 수 없다. (row의 차와 column의 차가 같은 경우)

---

풀이

기본적인 아이디어는 다음과 같다.

1. (정리 예정)

이를 구현한 코드는 다음과 같다.

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

public class Main {
    static int N;
    static int answer = 0;
    static int[] arr;
    
    public static void getN() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
    }
    
    public static boolean isPossible(int nowRow) {
    	int nowColumn = arr[nowRow];
    	for (int i = 0; i < nowRow; i++) {
    		if (arr[i] == nowColumn) {
    			return false;
    		}
    		if (Math.abs(arr[i] - nowColumn) == Math.abs(i - nowRow)) {
    			return false;
    		}
    	}
    	return true;
    }
    
    public static void addQueen(int nowRow) {
    	if (nowRow == N) {
    		answer += 1;
    		return;
    	} else {
    		for (int i = 0; i < N; i++) {
    			arr[nowRow] = i;
    			if (isPossible(nowRow)) {
    				addQueen(nowRow+1);
    			}
    		}
    	}
    }
    
    public static void main(String[] args) throws IOException {
        getN();
        
        arr = new int[N];
        
        addQueen(0);
        
        System.out.println(answer);
    }
}

---

회고

드디어 자바를 이용해 풀었던 (난이도가 조금 있는) 첫번째 문제에 도달했다.
아무래도 당시에는 자바 언어 활용이나 알고리즘 역량이 부족해서 코드가 그렇게 최선으로 짜여지지는 않은 것 같다.

일단 단순하게 다른 분들과의 풀이 시간을 비교해봐도 상당히 느리다.
나의 코드에서는 각 행에서 퀸을 배치할 때 이전의 행을 모두 훑지만, 이렇게 하지 않고 미리미리 사용가능한 열을 기록해서 퀸을 배치할 때 이를 피하도록 한다면 더 효율적으로 문제를 해결할 수 있다.