문제
입출력
골때리는 힌트!
풀이
지뢰찾기나 할 줄 알지 체스나 장기같은 멋진 게임에 대한 룰은 몰라서
일단 퀸이 어떻게 움직이는지 찾아봤다.
일단 퀸은 칸 수에 상관없이 상하좌우대각선으로 이동할 수 있다.
이 규칙에 기반하여 n개의 퀸이 서로의 이동경로에 있지 않도록 놓아야 한다.
그렇다면 0번째 열에 퀸은 몇 개 있을까? 바로 한 개다.
1번째 열에도, n번째 열에도 각 열에 놓을 수 있는 퀸의 개수는 하나다.
좌우로 움직이니 2개는 놓을 수 없고,
0개 혹은 1개를 놓아야 하는데 n*n 배열에 n개의 퀸을 두려면
각 열에는 반드시 1개의 퀸이 있어야 한다.
이 규칙으로 for문을 하나 줄일 수 있다.
이 때 col[n]은 n번째 열에 위치한 퀸의 row 값을 의미한다.
초기에 col의 모든 값을 -1로 초기화한다.
재귀함수에 들어가서, col[열] 값이 r일 때 check 함수를 통과하면 그 다음 열에 대한 재귀함수를 돌린다.
c가 n과 같을 때, 즉 모든 열에 퀸이 세워지면 return하여 경우의 수를 구할 수 있다.
check 함수는 이번에 놓은 퀸이 여태껏 둔 퀸들의 이동경로에 위치하지 않는지를 확인한다.
행의 값이 겹치면 false를 return하고
대각선에 위치하면 false를 return하며
모든 for문을 통과하면 true를 return한다.
이 때 대각선에 위치하는 두 좌표의 x좌표 차이와 y좌표 차이의 절댓값이 같다는 사실을 이용할 수 있다.
두 좌표를 기준으로 삼각형을 그려보면 쉽게 이해할 수 있다.
완전히 심하게 이해한 상태는 아니라 다음에 보면 백퍼 까먹을 것 같은데
일단 4일 전에 쳤던 코드라 그런지 지금은 기억이 난다.
4주가 지나면 어떻게 될가 (뻔함)
코드
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int n;
int col[15];
bool check(int c) {
for (int i = 0; i < c; i++) {
if (col[c] == col[i]) return false;
if (abs(col[c] - col[i]) == c - i) return false;
}
return true;
}
int solution(int c) {
if (c == n) return 1;
int cnt = 0;
for (int r = 0; r < n; r++) {
col[c] = r;
if (check(c)) cnt += solution(c + 1);
col[c] = -1;
}
return cnt;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
fill(col, col + 15, -1);
cout << solution(0);
return 0;
}채점
ios::sync_with_stdio(false); cin.tie(0);
이 코드 만능인 줄 알았는데 희한하게도 시간이 조금 더 오래 걸렸다.
