[SWEA] 2806 - N-Queen

안녕하세요, Einere입니다.

(ADblock을 꺼주시면 감사하겠습니다.)

---

이번 포스트에서는 삼성 SW Expert Academy의 2806번 문제인 N-Queen에 대해 알아보도록 하겠습니다.

 

 

회의 시간 : 2019.11.03 13:00 ~ 15:00

회의 장소 : 강남역 SG스터디룸

 

 

접근 방법

N-Queen 문제는 백 트래킹의 대표적인 문제입니다. 알고리즘 수업때 한번쯤 배우고 지나갑니다.

제가 생각하는 키 포인트는 다음과 같습니다.

• 백 트래킹 : 퀸을 특정 위치에 놓아 보고, 조건에 맞지 않다면 퀸을 치우고 다른 자리에 놓아 봅니다.
• 퀸을 놓을 위치 : 문제에서 퀸들은 서로를 공격할 수 없어야 합니다. 즉, 특정 위치가 안전한 자리인지 확인해야 합니다.

위 두 키 포인트를 위해, column라는 자료구조가 필요합니다. column은 각 행마다 놓여진 퀸의 열을 저장합니다. 예를 들어 columns = [2, 3, 1, 2]는 (1, 2), (2, 3), (3, 1), (4, 2)에 퀸이 놓여있다는 뜻입니다.

 

 

백트래킹

백트래킹은 다양하게 구현할 수 있습니다만, 해당 문제에서는 단순히 이전 상태를 새로운 상태로 덮어쓰는 방식으로 백트래킹을 구현하겠습니다.

 

 

퀸

체스에서 퀸은 8방향으로 거리 제한 없이 이동할 수 있습니다. 이것을 이용해 안전한 자리인지 확인하는 방법은 크게 두가지로 나뉩니다.

• 해당 행에 다른 퀸이 존재하는지 확인합니다.
• 해당 열에 다른 퀸이 존재하는지 확인합니다.
• 이전에 배치한 퀸의 대각선상에 존재하는지 확인합니다. 이는 두 퀸을 이용해 직각 삼각형을 그렸을 때, 밑변과 높이가 동일한 지 확인하면 됩니다.

 

 

풀이 코드 (java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Solution {
    private int testCaseNumber;
    private int[] Ns;
    private int[] cols;
    private int count;
 
    public void main() {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        try {
            testCaseNumber = Integer.parseInt(br.readLine(), 10);
            Ns = new int[testCaseNumber];
            for(int i = 0; i < testCaseNumber; i++) {
                Ns[i] = Integer.parseInt(br.readLine(), 10);
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
 
        for (int i = 0; i < testCaseNumber; i++) {
            cols = new int[Ns[i] + 1];
            queen(0, Ns[i]);
            System.out.println(String.format("#%d %d", i+1, count));
            count = 0;
        }
    }
 
    // 임의의 열에 퀸을 배치한 row에 대해, promising한지 검사합니다
    private void queen(int row, int N) {
        // 배치된 퀸이 다른 퀸과 충돌하는 경우
        if (!promising(row)) return;
 
        // 다른 퀸과 충돌하지 않으면서, 마지막 행에 퀸을 배치한 경우
        if (row == N) {
            count++;
        } else {
            for (int i = 1; i <= N; i++) {
                // 현재 행까지는 배치가 완료되었으며, 다음 행에 임의로 배치 후 promising한지 검사합니다
                cols[row + 1] = i;
                queen(row + 1, N);
            }
        }
    }
 
    // 해당 함수가 호출된 row에 대해, row-1번째 퀸까지는 정상적으로 배치되었음을 전제로 합니다.
    // 즉, row번째 퀸과 그 이전의 퀸들과 충돌 여부만 검사하면 됩니다.
    private boolean promising(int row) {
        // 0번째 행에는 퀸을 배치하지 않으므로, true를 반환합니다
        if (row == 0) return true;
 
        for (int i = 1; i < row; i++) {
            // 같은 열에 다른 퀸이 존재하는지 검사합니다.
            if (cols[row] == cols[i]) return false;
            // 대각선에 다른 퀸이 존재하는지 검사합니다.
            else if (row - i == Math.abs(cols[row] - cols[i])) return false;
        }
        return true;
    }
}

그런데 제출을 해보면 런타임 에러(메모리 관련)이 뜨네요..