문제 개요
오늘의 코딩 테스트 문제는 백준의 N-Queen 문제다. 체스판에 N개의 퀸을 서로 공격할 수 없게 배치하는 경우의 수를 구하는 문제다.
문제 분석
•
N x N 체스판에 N개의 퀸을 배치
•
퀸은 서로 공격할 수 없어야 함 (같은 행, 열, 대각선에 위치 불가)
•
가능한 모든 배치 방법의 수를 구해야 함
입력은 체스판의 크기 N (1 ≤ N < 15)이고, 출력은 가능한 배치 방법의 수다.
접근 방식
DFS와 백트래킹을 사용해 모든 경우의 수를 탐색하기로 했다. 각 행마다 퀸의 열 위치를 결정하면서 진행한다.
1.
각 행에서 퀸의 열 위치 선택
2.
이전에 선택된 열이나 대각선에 있는 경우 제외
3.
N개의 퀸을 모두 배치할 수 있으면 카운트 증가
구현
#include <iostream>
#include <vector>
using namespace std;
int N;
int count = 0;
void dfs(vector<int> visited, int level)
{
if (level>=N)
{
count++;
return;
}
// 가능한 열 탐색
for (int i = 0; i < N; i++)
{
bool found = false;
// 같은 열이 있으면 안됨
for (int j = 0; j < visited.size(); j++)
if (visited[j] == i)
found = true;
// 대각선에도 있으면 안됨
for (int j = 0; j < visited.size(); j++)
if ((level-j) == abs(visited[j]-i))
found = true;
if (!found)
{
visited.push_back(i);
dfs(visited, level+1);
visited.pop_back();
}
}
}
int main()
{
cin >> N;
dfs({}, 0);
cout << count << endl;
return 0;
}
C++
복사
주요 로직:
1.
DFS 함수를 재귀적으로 호출하며 각 행의 퀸 위치 결정
2.
유효한 위치인지 확인 (같은 열, 대각선 체크)
3.
유효하면 다음 행으로 진행, 아니면 백트래킹
4.
N개의 퀸을 모두 배치하면 카운트 증가
회고
N-Queen은 전형적인 백트래킹 문제다. 예전에 풀어본 경험이 있어서 접근 방식은 금방 떠올랐다. 하지만 구현 과정에서 실수가 있었다. 대각선 체크 로직에서 절대값을 안써서 한 번 틀렸다.
이런 실수들은 코딩 테스트에서 시간을 낭비하게 만드는 요인이다. 기본적인 구현 능력을 더 연마해야겠다.
