프로그래머스 LEVEL 2(N-Queen)

image

  • 사용 언어 : javascript

  • 해결 날짜 : 2022-10-25

  • 해결 방법 :
    • 퀸은 하나의 열 당 하나씩밖에 놓지 못함
    • 첫번째 행부터 dfs에 집어넣음
    • dfs의 종료 조건은 마지막 행일때 (row가 n일 때)
    • 현재 행의 모든 열을 돌며 퀸을 놓고 (board[row] = col)
    • board의 이전 행들과 값을 비교하여 현재 놓은 위치가 올바를 때 다음 열에 대한 dfs 수행
      • 이 때 올바르지 않은 조건은 이전 행들과 같은 열에 있거나, 대각선에 위치한 경우
  • 회고 :
    • 처음에 당연히 2차원 배열로 방문 여부를 체크하여 풀려고 했는데 더 간단한 방법이 있었다.
    • 천천히 풀이 방법 생각하고 풀기..

  • 코드

    function solution(n) {
    let answer = 0;
    const board = [];
        
    const validation = (cur) => {
        for (let prev = 0; prev < cur; prev++) {
            if (board[prev] === board[cur] || Math.abs(board[cur] - board[prev]) === (cur - prev)) return false;
        }
        return true;
    }
        
    const dfs = (row) => {
        if (row === n) {
            answer++;
            return;
        }
            
        for (let col = 0; col < n; col++) {
            board[row] = col;
            if (validation(row)) dfs(row + 1);
        }
    }
        
    dfs(0);
        
    return answer;
}
  • 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges