백준 9663 - N-Queen

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

9663번: N-Queen

레이튼 교수에서 풀 땐 쉬웠는데..

 

0. 재귀를 통해 가능한 모든 경우를 시도(브루트 포스)하여 풀었다. 기본적인 문제 접근 방식은 다음과 같다.

 

크기를 입력받아 생성한 2차원 board 배열을 순회한다.

현재 위치에 퀸을 둘 수 있을 경우, 퀸을 그 자리에 놓고 이를 표시한 뒤, 바로 다음 행으로 이동한다. board의 마지막 행까지 도달했을 때 놓을 수 있는 자리가 존재한다면 경우의 수를 1 증가시킨다.

 

1. 재귀함수를 이용해 어찌저찌 코드를 다음과 같이 구성했다고 하자.

int placeQueen(const vector<vector<int>>& board, int row) {
	//base stage: 마지막 행 도달
	if (row == Size - 1) {
     	//놓을 수 있을 경우
		for (int j = 0; j < Size; j++) {
			if ...
            	return 1; //경우의 수 1 증가
		}
        //못 놓을 경우
		return 0;
	}

	//전체 경우의 수
	int res = 0;

	for (int j = 0; j < Size; j++) {
		if { //board[row][j]에 놓을 수 있을 경우
			/*놓고 표시*/
            
            //재귀 : 다음 행으로 이동
			res += placeQueen(board, row + 1);
            
		}
	}

	return res;
}

이제 '놓을 수 있다'를 어떻게 구현하는 지가 문제 해결의 핵심이 될 것이다.

 

2. 이를 처음에 구현한 방법은 아래와 같다.

(0,0)에 위치한 퀸의 공격 가능 지점

이런 식으로.. 먼저 call by value로 board를 복사해왔다. 그리고 퀸을 둔 자리를 기준으로 퀸이 공격할 수 있는 상하, 좌우, 대각선에 flag를 표시하고 표시가 되어있는 board를 다음 함수에 전달했다.

 

이 방법에서 '놓을 수 있다' 란 board[i][j]의 flag가 1이라는 걸 뜻한다.

 

답은 맞은 거 같은데, 이렇게 구현하면 board에 표시를 할 때마다 call by value로 값을 일일히 복사해야 한다. 제출해보니 N의 크기가 커짐에 따라 수행시간이 크게 증가하더니 결국 시간초과가 떴다.

 

3. 퀸이 공격할 수 있는 모든 지점을 꼭 표시해두어야 하는 걸까? 생각해보니 그럴 필요가 없었다. 현재 퀸이 놓인 지점들만 알고 있으면 현재 위치가 퀸에게 공격받는 지점인지 board 배열 없이도 확인할 수 있다!

 

체스판 위에 퀸이 한 개 있고 그 좌표는 (2,2)라고 하자.

현재 위치가 공격받을 수 있는 경우는 위의 4가지이다.

1) 행이 같다 2) 열이 같다 3) 행+열이 같다 4) 행-열이 같다

 

이제는 board에 일일히 퀸의 이동범위를 표시하지 않고, queen의 좌표들을 저장할 별도의 배열을 생성하여 매 위치마다 이 배열만 확인하면 된다. 10X10 체스판 기준으로 확인해야 할 점의 개수가 100(표시하기 위한 call by value)에서 10(퀸의 최대 개수)으로 줄었다.

 

대신 call by value처럼, 이번 칸에서 퀸을 놓고 재귀함수 호출을 마치고 나면 다음 칸을 확인할 때는 방금 놓은 퀸을 치워야한다. 말로 설명하면 좀 헷갈려서 코드를 첨부한다.

for (int j = 0; j < Size; j++) {
    if (indep(queen, row, j)) { //놓을 수 있는 경우
        queen.push_back({ row,j });
        res += placeQueen(queen, row + 1);
        
        //다음 칸으로 이동하기 전 현 위치에 놨던 퀸 제거
        queen.pop_back(); 
    }
}

 

6.6초 걸리고 통과했다. N 값에 따른 수행시간 증가율을 보니 시간복잡도가 뭔가 O(N!)인 것 같다.

 

무서운 이야기) 이 글을 작성하기 시작했을 때 실행한 15-Queen 프로그램은 아직도 돌아가고 있음