문제

BOJ 9663: N-Queen https://www.acmicpc.net/problem/9663

풀이

• 1차원 배열을 만들어 배열의 index가 행을, map[index] 값이 열을 의미하도록 한다.

  예를 들어 1이 퀸이 있는 자리라고 했을 때 (N = 4)
  1 0 0 0
  0 0 0 1 ---------------------> map[] = {0, 3, 1, 2} 이다.
  0 1 0 0
  0 0 1 0

• isPossible(int x) 메소드를 통해 열, 대각선에 퀸이 놓일 수 있는지 확인한다.
  • 여기서 행은 map 배열에서 index를 통해 자동으로 구분이 되기 때문에 확인하지 않아도 된다.
• 퀸이 N개 놓일 때 까지 재귀 호출을 하여 답을 구한다.

코드

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

public class Main {
	
	static int N;
	static int[] map;
	static int cnt = 0;
	
	public static void main(String[] args) throws IOException{
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		sc.close();
		map = new int[N];
		
		bt(0);
		System.out.println(cnt);
	}
	
	static void bt(int depth) {
    	// 퀸을 N개 까지 다 놓으면 종료
		if(depth == N) {
			cnt++;
			return;
		}
		
		for(int j=0; j<N; j++) {
        	// depth 행의 j열에 퀸을 넣음
			map[depth] = j;
            // 넣은 퀸이 다른 퀸에게 공격받지 않으면 재귀호출
			if(isPossible(depth)) {
				bt(depth + 1);
			}
	
		}
	}
	
	static boolean isPossible(int x) {

		for(int i=0; i<x; i++) {
			// 같은 열에 있을 때
			if (map[x] == map[i]) {
				return false;
			} 
			// 대각선상에 놓여있는 경우
			// (열의 차와 행의 차가 같을 경우가 대각선에 놓여있는 경우다)
			else if (Math.abs(x - i) == Math.abs(map[x] - map[i])) {
				return false;
			}
		}
	
		return true;
	}
	
}

정리

• 2차원 배열을 통해 해결하려 했지만 실패하고 1차원 배열을 통해 해결하는 신선한 방법을 알게 되었다.
• index 를 통해 열을 구분하여 해결하니 가지치기가 효율적으로 되어 좋은 풀이가 되었다.