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

문제 번호

프로그래머스

 

 

 

알고리즘 분류

• 백트래킹

 

문제 풀이

 2차원 배열을 생성해서 퀸을 놓으면서 해당 퀸이 지나가는 경로를 체크해서 다음 퀸이 해당 경로에 올 수 없도록 하려고 했다. 그러나 2차원 배열을 그때그때 지워가면서 확인하려 했으나 그렇게 되면 시간 초과에 걸리게 된다.

 

 그래서 i번째 퀸을 놓을 수 있는지 다른 방법을 이용해서 확인해야 한다. 여기서 힌트를 읽어봤다. 1차원 배열을 사용하면 시간을 줄여서 확인할 수 있다. 예를 들어 'vailed [i] = 3'이라면 i행 3열에 퀸이 놓여있다는 뜻이다.

 

 이를 활용하여 세로, 왼쪽 대각선 아래, 오른쪽 대각선 아래를 확인할 수 있다. 대각선의 경우 '기울기'를 생각해 보면된다. (row, col)에 퀸을 놓고 싶다면 'vailed[i] - col'과 'i-row'를 비교해보고, 다시 이 값에 절댓값을 씌워서 비교해보면 양쪽 대각선을 확인할 수 있다.

function check(vailed, n, row, col){
    for(let i=0; i<row; i++) {
        if(vailed[i] == col) return false; // 세로.
        if(vailed[i]-col == i-row) return false; // 오른대
        if(Math.abs(vailed[i]-col) == Math.abs(i-row)) return false; // 왼대
    }    
    return true;
}

 

 이제 백트래킹을 수행하면서 모든 퀸을 조건에 맞게 놓을 수 있는지 확인하면 된다. 

 

처음 코드 (시간 초과)

/*
    1. 체스판과 크기가 같은 vailed를 만들어서 1개의 퀸을 놓을때 마다 vailed도 갱신한다.
    2. row에 더 이상 퀸을 놓을 수 없다면 pruning.
    3. 'row == 놓은 퀸의 수'라면 카운트를 증가시킨다.
*/
function solution(n) {    
  let vailed = new Array(n).fill(null).map(_ => new Array(n).fill(0));
  return back(0,n,0,vailed,0);    
}
function back(cnt,n,row,vailed,ret){        
  if(cnt == n) {
      //console.log('done!')
      return ret += 1;
  } else {
      for(let i=row ; i<n; i++) {
          for(let j=0; j<n; j++) {                                         
              if(!vailed[i][j]) {
                  mark(i,j,n,vailed,1); 
                  ret = back(cnt+1,n,i+1,vailed,ret);
                  mark(i,j,n,vailed,-1);
              }
          }
      }
  }
  return ret;
}
function mark(row,col,n,vailed,state){ // stata == 1 ? 퀸이 지나간자리 : 퀸을 회수함
  const i = 1;
  // 세로
  let [r,c] = [row,col];
  while(r < n) {                
      vailed[r][c] += state;        
      r += i;
  }
  // 좌아래 대각
  [r,c] = [row,col];
  while(r < n && c >= 0) {        
      vailed[r][c] += state;
      r += i;
      c -= i;
  }
  // 우아래 대각    
  [r,c] = [row,col];
  while(r < n && c < n) {        
      vailed[r][c] += state;
      r += i;
      c += i;
  }
  // 중복으로 계산된거 제외.
  [r,c] = [row,col];
  vailed[r][c] -= 2*state; 
  return;
}

 

전체 코드

/*
    1. 체스판과 크기가 같은 vailed를 만들어서 1개의 퀸을 놓을때 마다 vailed도 갱신한다.
    2. row에 더 이상 퀸을 놓을 수 없다면 pruning.
    3. 'row == 놓은 퀸의 수'라면 카운트를 증가시킨다.
*/
function solution(n) {    
    let vailed = new Array(n).fill(-1);
    return back(vailed, n, 0, 0, 0);
}
function back(vailed, n, row, cnt, ret) {    
    if(cnt == n){
        return ret += 1;
    }
    for(let col=0; col<n; col++) {
        if(check(vailed,n,row,col)) {
            vailed[row] = col;
            ret = back(vailed, n, row+1, cnt+1, ret);   
            vailed[row] = -1;
        }            
    }    
    return ret;
}
function check(vailed, n, row, col){
    for(let i=0; i<row; i++) {
        if(vailed[i] == col) return false; // 세로.
        if(vailed[i]-col == i-row) return false; // 오른대
        if(Math.abs(vailed[i]-col) == Math.abs(i-row)) return false; // 왼대
    }    
    return true;
}

 

 

특이사항

 문제에서 주어진 자료의 모양을 그대로 사용하기보다 접근하기 쉽게 사용해야할 필요성이 있다. 

다 빠르고 간단하게 사용할 수 있는 방법들을 항상 생각해보자.