N-Queen

티스토리 뷰

N-Queen

KidCat 2023. 2. 18. 18:42

N-Queen 문제는 백트래킹을 이용한 웰노운 문제 중 하나이다.

내 풀이가 다른 블로그들의 풀이와 차이가 좀 있어서 글을 작성하게 되었다.

웰노운 문제이고 풀이방법이 존재하는 이상 내 풀이가 다른 풀이보다 더 좋은 풀이가 아니다. 실제로 백준의 N-Queen 문제에서 돌려본 결과, 내 풀이가 시간이 더 오래걸리는 것을 확인했다.

처음 푼게 직접 푼 풀이이고, 2,3번째 풀이는 블로그 글을 참고해서 작성한 풀이이다. 백준에 치팅 ( 복붙 ) 으로 문제가 생길 수 있어서 주석으로 어디 블로그 풀이에서 도움을 받았는지 적어놓았다.

내 풀이를 설명하기 위해 체스판을 위에서 부터 1행, 2행 .. n행이라고 하고, 가장 왼쪽 열부터 1열,2열 .. n열이라고 하겠다.

여담으로 처음에는 DP로도 될것 같았다. 2*2 에 체스판이 있다고 하면, 왼쪽, 중간, 오른쪽 3군데에 체스판 열을 끼워넣으면 3*3 체스판이 된다. 2*2 체스판에는 끼워넣을 수 있는 곳이 3군데, 3*3 체스판은 4군데 .. 해서 N*N 체스판까지 늘려가자 라는 생각을 했지만, 점화식이 떠오르지가 않아서 바로 풀이법이 생각난 백트래킹으로 방향을 잡았다.

깊이 알아보지는 않아서, N-Queen 문제가 DP로도 풀릴 수 있는지는 잘 모르겠다. 백준 태그에 DP가 없는 걸 봐서는 안될 확률이 더 높아보인다.

내가 생각한 순서는 이렇다.

1. 1행에 퀸을 놓는다.

2. 이제 1행에는 퀸을 더 이상 놓을 수 없으므로, 2행에서 퀸을 놓아야 한다.

3. 하지만 1행에 놓은 퀸에 의해 2행에 퀸을 놓을 수 없는 자리가 존재하게 된다.

4. 이는 n행까지 계속된다. n행에 퀸을 놓으려면 1~n-1행의 퀸의 위치에 의해 n행에 퀸을 놓지 못하는 자리가 생긴다.

이런 이유로 백트래킹으로 구현을 하기로 했다. 다음행으로 넘어갈 때 마다 이전 행들에 의해서 제약이 생기므로, 제약때문에 퀸을 놓을 수 없다면 이전 행으로 돌아가자 라고 생각했기 때문이다.

처음에는 맵과 방문처리를 할 배열을 만들어준다. 문제에서는 ( 1<= N < 15 ) 이다.

int map[17][17];
int visited[17][17];
int n; // 체스판의 크기
int cnt = 0; // 퀸을 배치할 수 있는 경우의 수

다음에는 DFS 함수를 만드는데, 생각해야 될 것은 2가지였다.

1. 언제 cnt를 증가시킬 것인가.

- 체스판의 마지막 행에 도달했고, 퀸을 놓을 수 있다면 cnt++ 이 된다.

2. 방문처리

- 퀸은 가로,세로,대각선을 전부 올 수 없게 하므로 퀸을 놓은 위치에서 가로 세로 대각선을 전부 방문처리한다.

이 함수가 VT ( Visited True ) 함수이다.

- 백트래킹을 마치고 퀸을 다른 위치로 옮길 때는 이전에 True 체크한 곳을 다시 False 로 바꿔줘야 한다. 이 함수가 VF 함수이다.

void DFS(int k , int row ) { // K = 퀸을 놓은 개수, row = 탐색할 열
	if (k == n ) { // 퀸을 n 개 놓았다면 cnt++
		cnt++;
		return;
	}

	for (int i = 1; i<=n; i++) {
		if (!visited[row][i]) { 
			VT(row,i);
			DFS(k+1,row+1);
			VF(row,i);
		}
	}
}

여기서 방문처리는 퀸을 놓은 위치가 방문처리가 되는 것이 아니라, 퀸을 놓아서 더 이상 다음에 퀸을 둘 수 없는 곳을 전부 방문처리한다. 예를 들어 (1,1) 에 퀸을 놓았다면 1행, 1열과 (1,1) , (2,2) .. (n,n) 까지는 전부 방문처리가 된다.

for문은 방문처리가 안된 곳이라면 = 퀸을 놓을 수 있는 곳이라면 퀸을 놓는다.

VT = 퀸을 그 자리에 놓음으로써 퀸을 놓을 수 없게 된 곳을 전부 방문처리한다.

DFS(k+1,row+1) = 퀸을 놓았으므로 퀸의 개수 +1 ( k+1 ) , 다음 행을 탐색할 것이므로 행 + 1 ( row + 1 )

VF = 백트래킹을 하고 돌아왔다면, 방문처리한 곳을 다시 방문안했다고 체크.

첫번째 실패

방문처리에 있어서 문제가 생겼다. 백트래킹을 하면서 방문처리를 취소할 때, 이전 행에서 방문처리가 된 곳 까지 취소해버리는 문제가 발생했다.

예를 들어 (1,1) 과 (2,3) 에 퀸을 놓았다. 이후 3행에 대해서 탐색을 했는데, 더 이상 퀸을 놓을 수 없는 상황이 되었다고 하자. 그렇다면 (2,3)으로 돌아와서 방문처리한 곳을 취소하고 (2,4) 에 퀸을 놓고 다시 탐색을 할 것이다.

여기서 방문처리를 취소할 때, (2,3) 이 방문한 곳을 취소하면서 (1,1) 에 의해 방문처리가 된 곳 까지 같이 취소해버리는 것이다. 만약 (4,1) 이라는 위치가 있다고 하자. 이는 (2,3) 에 의해 방문처리가 되지만, (1,1) 에 의해서도 방문처리가 되는 위치이다. 따라서 (2,3) 으로 돌아와서 방문처리 한 곳을 취소할 떄 (4,1) 은 취소하면 안된다. (1,1) 에 의해 여전히 갈 수 없는 곳이다.

해결

방문처리를 할 떄 1과 0 ( true 와 false ) 로 방문처리를 하는 것이 아니라 row로 방문처리를 하는 것이다.

정리하자면 다음과 같은 순서로 방문처리를 한다.

실패 할 때 방문처리

1. 퀸에 의해 방문처리가 되어야 하는 위치인가요 ? -> yes

2. 해당 위치가 방문처리가 된다 = 해당위치를 true

수정한 방문처리

1. 퀸에 의해 방문처리가 되어야 하는 위치인가요 ? -> yes

2. (new) 해당 위치의 값이 0 ( 아직 방문한 적이 없다 ) 인가요? -> yes

3. 해당 위치가 방문처리가 된다 = 해당위치에 row 값을 넣는다.

이에 맞게 원래 방문취소 함수( VF ) 도 변경한다.

실패 할 때 방문취소

1. 방문처리가 된곳인가요? -> yes

2. 방문처리를 취소한다.

수정한 방문취소

1. 방문처리가 된곳인가요? -> yes

2. (new) 그 곳의 값이 row 인가요? -> yes

3. 방문처리를 취소한다.

이와 같은 방식으로 VT함수와 VF함수를 수정한 결과이다.

void VT(int row, int col) {
	for (int i = 1; i <= n; i++) {
		if (!visited[row][i])
			visited[row][i] = row;
		if (!visited[i][col])
			visited[i][col] = row;
	}

	/*
	* 
	..대각선에 대한 방문처리 코드

	*/ 
}


void VF(int row, int col) {
	for (int i = 1; i <= n; i++) {
		if (visited[row][i] == row)
			visited[row][i] = 0;
		if (visited[i][col] == row)
			visited[i][col] = 0;
	}

	/*
	
	대각선에 대한 방문 취소..

	*/

}

두번째 실패

방문처리 시간이 너무 길어서 시간초과가 발생했다. 실제로 제출해보진 않았고 N = 14를 넣고 출력을 확인해봤는데 거의 20초 가까이 걸려서 답이 나왔다.

처음에는 다음과 같은 방법으로 방문처리와 취소를 했다.

1. 현재 퀸이 ( i, j ) 의 위치에 있다.

2. i행과 j열을 전부 방문처리(취소) 한다.

3. ( i - k , j - k ) 를 전부 방문처리한다. 이 때 k값은 1부터 시작해서 1씩 증가하며, i -k 와 j-k <= 0 이 되면 탈출한다. 체스판이 없는 곳이다. 이걸로 퀸이 있는 위치에서 왼쪽 위로 향하는 대각선은 전부 방문처리(취소) 가 된다.

4. 3번 방법으로 오른쪽 위, 왼쪽 아래, 오른쪽 아래에 대해서도 방문처리(취소) 를 한다.

위 방법으로는 n = 12 부터는 시간이 너무 오래걸렸다. 제한시간이 10초인데도 통과 못할 것을 확신할 정도였다.

해결

행을 올라가는 방향으로는 방문처리나 취소를 할 필요가 없다는 것을 깨달았다.

예를 들어 내가 현재 (3,4) 의 위치에 퀸을 놓고, 방문처리를 한다고 하자. 그렇다면 1행과 2행은 이미 이전 DFS에 의해 전부 방문처리가 되어있다.

내가 DFS 를 할 때 1행 -> 2행 -> 3행 순으로 하고 있으므로, 1행 2행은 임의의 위치에 이미 퀸이 놓여있다. 그렇다면 1행과 2행의 모든 위치는 (3,4) 에 의해 방문처리되는 것 이전에 이미 방문처리가 무조건 되어있는 것이다.

따라서 왼쪽 위 대각선과 오른쪽 위 대각선 방향으로는 방문처리를 할 필요가 없다. 이미 이전 DFS에서 무조건 방문처리가 되었기 때문이다. 방문처리를 하지 않으므로 당연히 방문 취소를 할 필요도 없다.

원래 코드는 3,4번에 의해 FOR문을 4개 돌렸다. 수정한 후에는 왼쪽위와 오른쪽위 대각선, 즉 row 값이 감소하는 방향으로는 뻗어나가는 대각선에 대해서는 방문처리를 하지 않게 수정하였다. 결과적으로 FOR문이 2개로 감소했다.

수정된 코드이다.

for (int i = 1; ; i++) {
    int rr = row + i;
    int cc = col + i;
    if (rr > n || cc > n)
        break;
    if (!visited[rr][cc])
        visited[rr][cc] = row;
}

for (int i = 1; ; i++) {
    int rr = row + i;
    int cc = col - i;
    if (rr > n || cc < 1)
        break;
    if (!visited[rr][cc])
        visited[rr][cc] = row;
}

최종 답.

#include <iostream>
#include <vector>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

using namespace std;

int map[17][17];
int visited[17][17];
int n;
int cnt = 0;

void VT(int row, int col) {
	for (int i = 1; i <= n; i++) {
		if(!visited[row][i])
			visited[row][i] = row;
		if (!visited[i][col])
			visited[i][col] = row; 
	}
	
	for (int i = 1; ; i++) {
		int rr = row + i;
		int cc = col + i;
		if (rr > n || cc > n)
			break;
		if (!visited[rr][cc])
			visited[rr][cc] = row;
	}

	for (int i = 1; ; i++) {
		int rr = row + i;
		int cc = col - i;
		if (rr > n || cc < 1)
			break;
		if (!visited[rr][cc])
			visited[rr][cc] = row;
	}

}

void VF(int row, int col) {
	for (int i = 1; i <= n; i++) {
		if (visited[row][i] == row)
			visited[row][i] = 0;
		if (visited[i][col] == row)
			visited[i][col] = 0;
	}
	
	for (int i = 1; ; i++) {
		int rr = row + i;
		int cc = col + i;
		if (rr > n || cc > n)
			break;
		if (visited[rr][cc] == row)
			visited[rr][cc] = 0;
	}

	for (int i = 1; ; i++) {
		int rr = row + i;
		int cc = col - i;
		if (rr > n || cc < 1)
			break;
		if (visited[rr][cc] == row)
			visited[rr][cc] = 0;
	}

}

void DFS(int k , int row ) {
	if (k == n ) {
		cnt++;
		return;
	}

	for (int i = 1; i<=n; i++) {
		if (!visited[row][i]) {
			VT(row,i);
			DFS(k+1,row+1);
			VF(row,i);
		}
	}
}

int main() {
	fastio;

	cin >> n;
	DFS(0, 1);
	cout << cnt;
}

알려진 풀이를 찾아본 후기

1. 체스판의 위치 설정

- 나는 체스판에 퀸의 위치를 당연히 2차원 배열로 선언했다. ( 행과 열이 존재하므로 ) 하지만 알려진 풀이를 보니 1차원 배열로 퀸의 위치를 특정하고 있었다.

방법은 퀸이 ( i , j ) 위치에 있다면 Queen[i] = j 로 선언하는 것이다. 전혀 생각치도 못한 방법으로 2차원 좌표를 표기하고 있었다. 이 방법은 알아두면 다른 문제에서도 언젠가 쓸 수 있을 것 같아서 적어두기로 했다.

나는 '퀸을 놓는다' 라는 것은 무조건 표시해야 된다고 생각했다.

i번째 행 j 번째 열에 퀸이 있다 라고 표시할 값 k , 3개의 값을 저장해야 된다고 생각했지만 실제로는 그렇지 않았다.

i번째 행 j 번째 열에 퀸이 있다. 굳이 k라는 값이 필요가 없었다.

2. 대각선의 방문처리(취소)

나 같은 경우는 아래 방법으로 대각선 방문처리를 했다.

for (int i = 1; ; i++) {
    int rr = row + i;
    int cc = col + i;
    if (rr > n || cc > n)
        break;
    if (!visited[rr][cc])
        visited[rr][cc] = row;
}

for (int i = 1; ; i++) {
    int rr = row + i;
    int cc = col - i;
    if (rr > n || cc < 1)
        break;
    if (!visited[rr][cc])
        visited[rr][cc] = row;
}

row와 col 을 +1 또는 -1 해서 rr과 cc에 저장하고 rr 과 cc가 배열 범위에 벗어나지 않으면서, 0값이라면 row 값으로 방문처리를 해주는 것이다. 취소하는 방법도 마찬가지이다.

알려진 풀이에서는 다음 코드로 방문처리를 한다.

abs(col[i] - col[k]) == abs(i - k)

/*

해당 코드 출처는
https://code-lab1.tistory.com/17 입니다.

*/

( 행 - 행 ) 값이 (열 -열 ) 값과 같다면 대각선이는 것이다.

예를 들어 (1,1) 에서 대각선인 위치를 보자. (2,2) , (3,3) .. ( n,n) 이다. 따라서 임의의 대각선 위치 (k,k) 에서 (1,1) 을 행-행, 열- 열 한다면 그 값이 동일하다.

대각선을 체크하는 방법중에 하나를 새로 배웠다. 나중에 2차원 map에서 대각선을 체크하는 문제를 보게 된다면 다시 쓸 수 있다고 생각해서 1과 마찬가지로 기록해두기로 했다.

재밌게 풀기도 했고, 백트래킹 구현 실력을 올릴 수 있는 문제라고 생각한다. 웰노운 문제이니 알아두는 것도 나쁘지 않다고 생각한다.

이번에도 그렇지만 어떤 문제를 DP로 풀수 있는가? 를 확신을 못하겠다.

이 문제도 N =1 ,2 ,3 .. 순차적으로 증가하고 이전 체스판에서 저장된 결과를 이용할 수 있지 않을까? 하는 느낌이 뜨니까 바로 DP 문제라고 생각이 들어버렸다.

결과적으로 풀이법이 생각이 안나서 백트래킹으로 바꿔서 풀긴 했는데, DP 문제인지 아닌지 판단하는 실력을 더 길러야겠다..

의문

n = 15 일 때는 거의 40초를 기다려도 정답이 안나왔다. 답이 안나오길레 그냥 실행종료를 해버렸는데 얼마나 기다려야 답이 나올까.. n =14 랑 n = 15 의 차이는 얼마나 나는 걸까..

저작자표시 (새창열림)

'PS' 카테고리의 다른 글

[백준 2437] 저울 (2)	2023.09.02
[백준 9466] 텀 프로젝트 - 위상정렬 풀이 (0)	2023.08.13
[C++] 백준1025. 제곱수 찾기 (0)	2023.03.19

공지사항

최근에 올라온 글

최근에 달린 댓글

Total

Today

Yesterday

링크

TAG more

« 2025/09 »
일	월	화	수	목	금	토
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30

글 보관함

티스토리 뷰

N-Queen

'PS' 카테고리의 다른 글

티스토리툴바