[JS] 프로그래머스 - N-Queen

문제

정답 풀이

function solution(n) {
    var answer = 0;
    
    function check (v, r) {
        for (let j = 1; j < r; j++) {
            if (v[j] === v[r]) return false;
            if (Math.abs(j - r) === Math.abs(v[j] - v[r])) return false;
        }
        return true;
    }
    
    function dfs (v, row) {
        if (row === n) return answer++;
        
        for (let k = 1; k <= n; k ++) {
            v[row + 1] = k;
            if (check (v, row + 1)) dfs(v, row + 1);
        }
    }
    
    for (let i = 1; i <= n; i ++) {
        const visited = Array.from(Array(n + 1), () => 0);
        visited[1] = i;
        dfs(visited, 1);
    }
    
    return answer;
}

백트레킹의 대표적인 문제 N-Queen 입니다.

백트래킹(Backtracking)이란?

해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아갑니다.

즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적입니다.

이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미입니다.

일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 하므로 처리가 불가능 할 수도 있습니다. 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 됩니다.

출처

문제를 푸는 아이디어

• 첫번째 행에 전부 한번씩 queen을 놓아보면서 탐색을 시작합니다.
• 두번째 행부터 퀸을 놓을 수 없는 경우는 다음과 같습니다.
  1. 지금까지 놓인 퀸 중에 하나라도 같은 열에 있을 경우
  2. 지금까지 놓인 퀸 중에 하나라도 대각선에 위치할 경우

    function check (v, r) {
        for (let j = 1; j < r; j++) {
          	// 1. 지금까지 놓인 퀸 중에 하나라도 같은 열에 있을 경우 return false;
            if (v[j] === v[r]) return false;
          	// 2. 지금까지 놓인 퀸 중에 하나라도 대각선에 위치할 경우 return false;
            if (Math.abs(j - r) === Math.abs(v[j] - v[r])) return false;
        }
        return true;
    }

위 코드가 앞서 말한 2가지 조건을 처리해주는 함수입니다.

여기서 눈여겨 봐야할 것은 2번째 조건인데 대각선을 판별하는 방법은 아래와 같습니다.

출처

문제에서 주어진 정사각형을 보게 되면 row와 column의 차이가 같을 때, 대각선의 위치에 있다는걸 알 수 있습니다.

즉, 앞에 놓여진 퀸 중에서 2행 1열에 놓여진 퀸이 있다면 2 - 1 = 1이고 현재 4행 3열에 퀸을 놓을 수 있을지 확인할 때, 4 - 3 = 1이므로 서로 대각선에 있어서 놓을 수 없다는 뜻입니다.
행 열의 차이는 절대 값으로 변환 해주어 대각선 위치에 놓일 수 있는지 확인합니다.