[프로그래머스] N-Queen

1. 문제

---

프로그래머스

 

2. 풀이 과정

---

N X N 체스판에 N개의 퀸을 놓을 때 서로 공격하지 못하게 놓는 경우의 수를 구하는 문제이다.

 

N X N 체스판에 N개의 퀸을 놓는 것이기 때문에 각 행에 하나씩 퀸을 놓는다고 생각하면 된다.

단, 서로 공격하지 못하게 놓아야 한다.

 

그림으로 보도록하자

4 X 4 체스판에 4개의 퀸을 서로 공격 못하게 놓는다고 하면

 

1. 첫번째 행

퀸이 하나도 없기 때문에 공격여부를 따질 필요가 없다. 따라서 첫 번째 열에 놓았다.

 

2. 두번째 행

첫 번째 열과 두 번째 열에 놓게 되면 서로 공격이 가능하다.

따라서 세 번째 열에 두었다.

 

3. 세 번째 행

모든 열에 둘 수가 없다. 이 경우에는 다시 이전 행부터 다시 두어야 한다.

 

4. 두 번째 행 수정 후 세 번째 행

두 번째 행의 퀸의 위치를 4열로 옮겼다.

그 결과 세 번째 행의 퀸을 2열에 놓을 수 있게 됐다.

 

5. 네 번째 행

어느 곳에도 들어갈 수 없다. 

따라서 이전 행부터 다시 두어야 한다.

 

6. 첫 번째 행 수정

세 번째 네 번째 행 모두 둘 곳이 없다 따라서 첫 번째 행의 퀸을 2열로 수정한다.

 

7. 두 번째 세 번째 네 번째 행 - 배치 성공

두 번째, 세 번째, 네 번째 행에 퀸을 적절한 위치에 두었다.

모든 퀸을 두었으므로 성공적으로 퀸을 배치하였다. 

 

8. 또 다른 케이스

위의 과정을 계속해서 반복하다보면 하나의 케이스가 더 나온다.

 

따라서 N이 4일 때 정답은 2이다.

 

체스판에 퀸을 두는 모든 경우의 수는 재귀를 통해 구현할 수 있다.

또한 백트래킹을 통해 재귀의 효율을 증가시켜 구현할 수 있다.

해당 문제에서 유망함수는 '퀸을 해당 위치에 둘 때 다른 퀸과 서로 공격이 가능하면 백트래킹 한다.' 이다.

퀸을 놓을 수 있는 모든 경우를 체크하다가 유망함수 조건이 발생하면 백트래킹을 수행하면 효율적으로 문제를 해결할 수 있다.

 

이제 코드로 보자.

3. 내 코드

---

class Solution {
    private int cnt = 0;
    private int N;
    private boolean[][] visited;
    public int solution(int n) {
        N = n;
        visited = new boolean[n][n];
        n_queen(0);
        return cnt;
    }
    
    private void n_queen(int queen) {
        // 리턴 조건: 마지막 퀸을 놨을 때
        if(queen == N){
            cnt++;
            return;
        }
        
        for(int i = 0; i < N; i++) {
            if(canPlace(queen, i)) {
                visited[queen][i] = true; // 퀸 배치
                n_queen(queen + 1);
                visited[queen][i] = false; // 퀸 배치 해제
            }
        }
    }
    
    private boolean canPlace(int row, int col) {
        // 세로
        for(int i = 0; i < N; i++) {
            if(i != row && visited[i][col]){
                return false;   
            }
        }
        
        // 대각선
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                
                // 1. 우측 대각선: 뺀게 같음
                // 2. 좌측 대각선: 더한게 같음
                if(row - col == i - j || row + col == i + j) {
                    if(visited[i][j]){
                        return false;
                    }
                }
            }
        }
        
        return true;
    }
}

시간 복잡도

• O(N!)

각 행에선 N개의 자리에 놓을 수 있다. 이러한 행이 N개 있는 것이므로 O(N!)이다.

하지만 백트래킹을 사용하므로 실질적인 시간복잡도는 이보다 낮다.

 

4. 피드백

---

• 재귀 함수에서 백트래킹을 이용하면 연산의 효율을 증가시킬 수 있다.