알고리즘

[JavaScript] N-Queen 문제 (백준9663, 프로그래머스)

Junly_21 2023. 10. 2. 19:33

백트래킹에서 매우 유명한 N-Queen문제를 풀었다.

몇 달 전에 머리 싸매면서 DFS, BFS이론을 공부한 뒤에 백준에서 골드4 N-Queen을 바로 접했을 때 벽을 엄청 느꼈었는데, 

 

최근에 알고리즘을 고민하며 푸는 맛에 좀 재미가 들렀고, N-Queen문제를 프로그래머스에서 다시 접하게 되어 각잡고 풀어보았는데 풀려서 접근 과정과 코드를 기록하려고 한다.

 

N-Queen 프로그래머스 링크

N-Queen 백준 링크

 

 

접근)

  1. 이미 실패했던 경험을 통해 유명한 DFS 백트래킹 문제임을 이미 알고있긴 했으니 DFS 백트래킹을 어떻게든 사용하여 구현하는데에 초점을 두었다 (솔직히 문제를 보자마자 아~ 백트래킹이구나~ 알아챌 자신은 없다.)
  2. 재귀의 형태던 while(stack.length>0)의 형태던 반복을 돌아야 하는것은 확실
  3. 어떠한 판단 함수가 있고, 이 판단함수의 depth가 n과 같은 상태에서도 퀸을 둘 수 있으면 방법 1개를 찾은 것이다.
  4. 판단 함수 내부에서는 적절히 if와 for문을 돌리며 내 depth(가로줄,row)에서 어디column 에 둘 수 있는지 확인하고 visited배열에 내가 퀸을 둔 위치를 체크하고 다음 depth로 넘어간다.

    만약 내 depth에서 둘 수 없다면 이전 단계에서 뒀던 걸 지워야한다 (이부분이 백트래킹)

이렇게 노트에 끄적이며 의사 코드를 작성하였다

 

의사코드

depth가 체스Table에서 두어지는 위치의 row 역할,

반복을 도는 i는 그 depth에서의 column의 역할을 맡고 있다는 점을 알고 들어가야한다

 

visited = [ ]  '이미 두어진 체스말 좌표 저장배열' 
dfs(단계){
 (for column in T)   'T는 Table의length, column는 두고싶은 위치의 '열'을 의미. 
체스판의  length만큼 이번 depth[행]의 column[열]을 모두 확인하겠다.'
   {
    for(visited 내부의 점좌표와 현재 [depth, column]좌표의 관계를 하나씩 확인한다){
            if (만약 visited 내부에 이미 있는 점과 (대각선 or 같은열)에 위치해있다면) {
            이 [depth][column]점에는 둘 수 없으므로 다음 column로 넘어간다. 
             }
          }
    (바로 위 for문을 다 통과해서 만약 둘 수 있는 점이 확인되었다면) {
           visited배열에 현재 row,colum (depth, column)를 추가한다.
           dfs(다음단계)
         }
    (둘 수 있는 점이 확인되었는데 이게 마지막 단계였으면) {
           result += 1
         }
   }
}

 

노트에 약 1시간 가량 끄적이며 고민하다보니 이런식으로 대략 로직이 완성되었고, 이를 구현해낼 수 있을까? 라는 생각이 들었지만 천천히 구현하였고 다행히도 성공했다.

 

코드는 다음과 같다

function solution(n) {
  var answer = 0;
 
  let visited = [];
  function dfs(depth) {
    for (let column = 0; column < n; i++) { //의사코드상 for column in T가 시작되는 지점
      let checkOK = true;
      for (const [row, col] of visited) {
        if (Math.abs(row - depth) === Math.abs(col - i) || i === col) {
          //대각선 상에 있거나, col이 같은게 하나라도 있으면
          checkOK = false;
        }
      }
      if (checkOK === true && depth < n - 1) {
        //이 [depth][column]에는 두는게 가능함
        visited.push([depth, column]);
        //console.log(visited);
        dfs(depth + 1);
      } else if (checkOK === true && depth === n - 1) {
        answer += 1;
      }
    }
    visited.pop();
  }
  dfs(0);
  return answer;//console.log(answer)로 확인 가능
}

어려웠던 부분

한 [depth]번째 가로줄에서[column]를 하나씩 증가시키며 둘 수 있는지 여부를 체크한 뒤에

모든 column에 둘 수 없면 visited에서 이전 좌표를 pop해주는 반면

둘 수 있는 칸이 있다면 다음depth의 dfs로 가도록 하는 부분이

코드를 짜다가 살짝 막혔는데, checkOK라는 flag를 설정함으로서 구현에 성공할 수 있었다.