프로그래머스 - N-Queen(Level 3)/Wanna Be 컴잘알

문제 출처- https://programmers.co.kr/learn/courses/30/lessons/12952#

코딩테스트 연습 - N-Queen | 프로그래머스

 

-문제-

 

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.

 

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.

제한사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

---

입출력 예

n	result
4	2

 

-접근-

 

1. bool check[12][12] 라는 놓을 수 있는지 놓을 수 없는지를 저장하는 변수를 하나 만듭니다.

2. 퀸이 움직일 수 있는 반경은 가로, 세로, 대각선이므로 특정 자리에 놓았을 때, 그 자리에서 퀸이 이동할 수 있는 지점은 모두 True처리를 해줍니다. => impossible_check 함수를 통해 set으로 저장 

3. set으로 저장하는 이유는 특정 자리에 놓은 퀸을 뺀다면 다시 그에 영향받는 다른 자리를 True->False로 돌려놔야 하기 때문입니다.

4. impossible_check 함수에서 s.insert를 하기전에 if(!check[][])를 해주는데 이 이유는 이미 해당 현재 퀸의 영향이 아닌 그 훨씬 더 이전에 놓은 퀸의 영향으로 놓을 수 없는 자리이므로 해당 자리는 insert시켜주지 않습니다.

 

★. 언뜻보면 간단해보이지만 해결 방법이 잘 떠오르지 않았지만 3,4번의 방법만 잘 기억해 놓으면 금방 풀 수 있을 것입니다.

 

-코드-

#include <string>
#include <vector>
#include <set>
#include <iostream>

using namespace std;
//nxn일 때, n개의 퀸으로 안겹치게 배치하는 방법
bool check[12][12];
int answer = 0;


set <pair<int,int>> impossible_check(int y, int x, int n) {
	set <pair<int,int>> s;
	
	//가로
	for (int i = 0; i < n; i++) {
		if(!check[y][i])
			s.insert({ y,i });
	}
	//세로
	for (int i = 0; i < n; i++) {
		if (!check[i][x])
			s.insert({ i,x });
	}
	for (int i = 0; i < n; i++) {
		//왼쪽위대각
		if (y - i >= 0 && x - i >= 0 && y - i < n && x - i < n) {
			if (!check[y-i][x-i])
				s.insert({ y - i,x - i });
		}
		//오른쪽위대각
		if (y - i >= 0 && x + i >= 0 && y - i < n && x + i < n) {
			if (!check[y-i][x+i])
				s.insert({ y - i,x + i });
		}
		//왼쪽아래대각
		if (y + i >= 0 && x - i >= 0 && y + i < n && x - i < n) {
			if (!check[i][x-i])
				s.insert({ y + i,x - i });
		}
		//오른쪽아래대각
		if (y + i >= 0 && x + i >= 0 && y + i < n && x + i < n) {
			if (!check[y+i][x+i])
				s.insert({ y + i,x + i });
		}
	}

	return s;
}

void dfs(int y, int x, int n, int cnt) {
	if(check[y][x] == false && x<n) {
		
		if (cnt == n - 1) {
			answer += 1;
			return;
		}

		set <pair<int, int>> s = impossible_check(y, x, n);
		for (auto i : s) {
			int yy = i.first;
			int xx = i.second;
			check[yy][xx] = true;
		}
		
		for (int k = 0; k < n; k++) {
			dfs(k, x + 1, n, cnt + 1);
		}

		for (auto i : s) {
			int yy = i.first;
			int xx = i.second;
			check[yy][xx] = false;
		}
	}

}

int solution(int n) {

	for (int i = 0; i < n; i++) {
		dfs(i, 0, n, 0);
	}

	return answer;
}