[코딩테스트]백준 - 스도쿠(2239)

diddnjs02·2020년 6월 30일
0

백준온라인저지

목록 보기
13/26
post-thumbnail

비슷한 문제 - 스도쿠(2580)

스도쿠

문제

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

입력

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

출력

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

예제 입력 1

103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

예제 출력 1

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

출처

ICPC > Regionals > Europe > Southeastern European Regional Contest > SEERC 2005 C번

  • 문제의 오타를 찾은 사람: kcm1700

링크

  • ACM-ICPC Live Archive
  • PKU Judge Online
  • ZJU Online Judge
  • TJU Online Judge

알고리즘 분류

  • 백트래킹

해결한 코드

function b2239(){
  var fs = require('fs');
  var input = fs.readFileSync('/dev/stdin').toString().split('\n');
  // var input = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "").split('\n');
  var link = []
  for (var k = 0; k < input.length; k++) {
      link.push(input[k].split('').map(e=>e/1))
  }
  var emptyArray = whereIsEmptyPoint(link) // 스도쿠 빈칸에 해당하는 좌표들 
  var ans = []
  fillSudoku(0, emptyArray, link, ans) // 빈칸 배열의 첫번째부터 fillSudoku 시작 !
}

function whereIsEmptyPoint(link){
  // 스도쿠 빈칸이 어디인지 
  var emptyArray = []
  for(var i=0; i<9; i++){
    for(var j=0; j<9; j++){
      if(link[i][j] === 0) emptyArray.push([i, j]) // link(i,j)가 빈칸이면 emptyArray에 (i,j) 추가
    }
  }
  return emptyArray
}

function fillSudoku(index, emptyArray, link, ans){
  
  if(index === emptyArray.length){
    // 빈칸을 다 채우면 
    for(var a=0; a<9; a++){
      for(var b=0; b<9; b++){
        ans.push(link[a][b]) // ans에 push
      }
      console.log(ans.join(''))
      // ans에 9개의 숫자가 담기면 공백없이 붙여서 출력하기 
      ans = []
      // 다음 행을 위해 배열 초기화 
    }
    process.exit(0)
    // 9x9칸 출력 다하면 프로세스 종료 
  }
  
  var x = emptyArray[index][0] // 스도쿠 빈칸에 해당하는 좌표의 x축 
  var y = emptyArray[index][1] // 스도쿠 빈칸에 해당하는 좌표의 y축
  
  for(var i=1; i<=9; i++){
    if(isPromising(x, y, i, link)){ // 1~9 중의 숫자 중 하나인 i를 link(x,y)에 넣어도 되면
      link[x][y] = i // i 넣기 
      fillSudoku(index+1, emptyArray, link, ans) // 다음 빈칸을 채우기 위해 재귀 함수 소환 
      link[x][y] = 0 // 근데 (안맞아서)돌아오면 0으로 초기화 
    }
  }
}

function isPromising(x, y, num, link){
  // fillSudoku 함수에서 부른 i는 num으로 들어옴  
  for(var i=0; i<9; i++){
    if(link[x][i] === num) return false // 같은 행에 1~9중 num으로 들어온 숫자가 있으면 false
  }
  
  for(var j=0; j<9; j++){
    if(link[j][y] === num) return false // 같은 열에 1~9중 num으로 들어온 숫자가 있으면 false 
  }
  
  var sx = Math.floor(x/3)*3
  var sy = Math.floor(y/3)*3
  // link(x,y)가 위치한 3x3 사각형 내 숫자 확인 
  for(var a=sx; a<sx+3; a++){
    for(var b=sy; b<sy+3; b++){
      if(link[a][b] === num) return false // 3x3사각형 안에 num으로 들어온 숫자가 있으면 false
    }
  }
  return true // 해당사항 없으면 true 
}

알고리즘

스도쿠(2580)와 풀이가 같다.
자세한 내용은 코드 내 주석으로 달았다.

스도쿠 문제를 통해 백트래킹에 대한 감을 조금씩 잡아가는 것 같다. 빠샤 ! 👊🏻

profile
개발 공부하는 심리학도

0개의 댓글