[CodeKata] 프로그래머스(Lv3) : N-Queen

🥋 Oooth More!! (Level 3) 

 

 

 

🧮 풀이

DFS를 통해 문제를 풀이해보았다.

처음엔 n x n의 2차원 board를 넘기려했으나 n에 따라 시간복잡도가 제곱배로 증가할 것으로 예상되었고 1차원 배열로 Queen들의 좌표를 관리했다.

function solution(n) {
  let answer = 0;
  
  function dfs(queens, row) {
    if (queens.length === n) {
      answer++;
      return;
    }
    
    for (let col = 0 ; col < n ; col++) {
      if (queens.includes(col) || queens.filter((qc,qr) => Math.abs(qc-col) === row - qr).length > 0) continue;
      dfs([...queens, col], row+1)
    }
  }
  
  dfs([], 0)
  
  return answer;
}

• answer은 정답을 누적할 변수다. dfs를 통해 모든 queens들이 조건에 만족한다면, answer에 1을 더할 것이다.
• 다음으로, dfs() 함수를 설계했다. 인자는 queens(queen들의 열좌표 모음), row(현재 행) 2가지를 받는다.
• queens를 좀 더 구체적으로 설명하겠다. 입출력 예의 첫 번째 정답은 [1,3,0,2] 로, 각 Queen은 0행1열, 1행3열, 2행0열, 3행2열 에 있다는 의미이다. 즉, queens의 인덱스는 행, 요소값은 열 번호를 의미하는 것이다.
• queens의 길이가 n과 같으면, 중간의 선별조건에 걸리치 않는 Queen들의 배치를 완료한 것이다. answer에 1을 더하고 종료한다.
• 다음으로, 0부터 n까지 col(열번호)을 순회하며 선별조건을 탐색한다.
  1. 첫번째는, queens가 col를 이미 가지고 있는 경우로, 이 땐 열이 겹치기 때문에 제외(continue)한다.
  2. 두번째는, queens의 queen들 중 (열번(qc) - 현재열(col)) 의 절대값과 (현재행(row) - 행번(qr))이 같은 경우다. 이 땐, 대각선이 겹치기 때문에 제외한다.
• 위 선별조건에 걸리지 않으면, 다음 dfs()에 진입한다. 현재 queens에 col을 넣어주고, row는 1을 더해 인자로 전달한다.
• 이제 dfs를 실행해주면 된다. 0번째 행은 걸릴 조건이 없으므로, [0] ~ [n]까지 다음 dfs() 로 진행되게된다.

 

 

🖇 리뷰

다른 풀이들도 DFS를 적용하기에 별도로 가져오지 않았다.

맨 처음에 0부터 n까지 순회하며 dfs([i], 1)로 시작하는것도 되지만, 나는 위처럼 0번째 행은 이상없이 순회되는 것을 알아 반복문을 2번 반복하지 않는 깔끔한 풀이가 되었다! 😁😁