[PS] N-Queen

프로그래머스

문제

- n*n 크기에 n개의 퀸을 배치할 수 있는 경우의 수 구하기

 

풀이

이 문제는 백트래킹으로 풀 수 있는 문제다.

즉 다음 좌표들의 방문 가능 여부를 체크하고, 불가능하면 다시 돌아와서 백트래킹한다.

 

1. 행 & 열 - 배치 가능 여부 확인

0행 1열에 퀸이 있으면 0행과 1열에는 배치 불가능하기 때문에

얼핏 보면 2차원 배열로 각각 모든 행과 열에 배치 가능한지 여부를 판단해야 할 것 같은데, 그렇지 않다.

1차원 배열로도 구현 가능하다!

 

Vector<bool> Move(n, false)

 

n 크기를 가진 Move 배열이 있다.

0행의 1열에 배치하면, Move[0] = 1 과 같은 형태로 저장할 수 있다.

즉 배열의 인덱스가 행이 되고, 값이 열이 되는 것이다.

 

2. 대각선 - 배치 가능 여부 확인

해당 열 배치 가능 여부는 Move 벡터에 저장된 bool 값으로 확인하고, 대각선으로 인한 배치 가능 여부는 따로 확인한다.

처음에는 Move 배열에 대각선으로 인한 배치 가능 여부까지 저장하려 했으나, 조건도 많고 경우가 많아서 비효율적일 것 같아서 다른 방법을 생각했다.

 

대각선으로 인한 배치 가능 여부는 "기울기"로 체크 가능하다.

지금까지 배치한 각각의 퀸의 위치와, 현재 배치하려는 퀸의 위치를 비교해서 기울기가 1이라면 배치 불가능하다.

 

이 조건들을 참고해서 DFS를 작성하면 쉽게 답을 구할 수 있다.

 

예시

n=4일 때, 두 가지 경우를 구할 수 있다.

코드

#include <string>
#include <vector>
using namespace std;

bool crossCheck(int row, int col, vector<int>& Location){
    for (int prevRow = 0; prevRow < row; prevRow++) {
        int prevCol = Location[prevRow];
        
        if (abs(row - prevRow) == abs(col - prevCol)) {
            return false;
        }
    }
    
    return true;
}

void dfs(vector<int>& Location, vector<bool>& Move, int n, int row, int& answer){
    if (row == n) {answer++; return;}
    
    // 이 행에서 방문 가능한 열이 있는지 체크
    for (int col = 0; col < n; col++){
        if (!Move[col]) continue;
        if (!crossCheck(row, col, Location)) continue;
        
        // 방문 가능하다면 방문
        // 퀸의 가로위치 전부, 퀸의 세로 위치 전부 방문 불가능 체크
        Location.push_back(col);
        Move[col] = false;
        
        dfs(Location, Move, n, row + 1, answer);
        Location.pop_back(); 
        Move[col] = true;
    }
}

int solution(int n) {
    int answer = 0;
    
    vector<int> Location;
    vector<bool> Move(n, true);
    // Location {1, 3, 0, 2}
    // Location[0] = 1, 0번째 행에서 1번째 열에 퀸이 위치
    
    dfs(Location, Move, n, 0, answer);
    
    return answer;
}

 

 

회고

최근에 DFS를 풀면서 백트래킹 문제가 어려워서 직접 찾아서 풀게 됐다!

이런 문제는 구현하는 재미가 있는 것 같다