[백트래킹] 백준 2580번 스도쿠 자바(java) 풀이

BOJ 2580번 스도쿠 자바(java) 풀이

백트래킹의 대표적인 문제중 하나라고 할 수 있습니다.
백트래킹 문제에 익숙하지 않다면 N-Queen 문제와 이 문제를 꼭 풀어보시기 바랍니다.

• 난이도: 골드4
• BOJ 2580번 스도쿠
  

문제 정리

1. 9x9 판으로 이루어진 판에 1~9 까지의 숫자들이 써있다.
2. 나머지 빈 칸을 채우는 방식은 다음과 같다.
   • 각각의 가로줄과 세로줄에는 1~9까지의 숫자가 한 번씩만 나타난다.
   • 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1~9 까지의 숫자가 한 번씩만 나타난다.
3. 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.
4. 스도쿠 판을 채우는 방법이 여럿인 경우 그 중 하나만을 출력한다.
   
   
   

문제 풀이

n-queen 문제와 유사한 방식으로 백트래킹을 이용하여 문제를 해결합니다.
백트래킹으로 가능한 모든 경우를 탐색하면 됩니다.

1. 완전 naive하게 값을 놓으려는 위치에 해당하는 행, 열, 박스를 모두 검사합니다.
2. 각 행, 열, 박스의 숫자가 쓰여져있는지 여부를 판단하느 boolean type의 visited 배열 형태를 만들어서 값을 쓸 수 있는지 아닌지 계산한다.

2번 방법으로 문제풀이를 시도하다가 박스의 인덱스를 어떤 수식으로 해야할지 감이 안와서 1번 방법으로 naive하게 풀이 하였습니다.

1. isValid 함수를 통해 행, 열, 박스안에 같은 값이 있는지 판단하여 없다면 sdoku 배열에 값을 써넣습니다.
   isValid 함수는 if문을 중첩하여 모든 경우의 수를 나누어 검사하였습니다.
2. 그리고 다음에 놓을 위치를 list에서 꺼내서 재귀적으로 호출합니다.
3. cnt 값이 list의 크기보다 1 작은 값이라면 이제 마지막 빈 칸에 값을 쓸 차례입니다. 마지막 칸에 값을 쓸 수 있는지 검사하여 씁니다.
   만약에 값을 쓸 수 없다면 그 자리의 값은 0이 되므로 return 하여 다른 경우의 수를 찾아봅니다.
   그렇지 않다면 스도쿠 배열을 출력하고 프로그램을 종료합니다.
   

• 박스의 인덱스 참조: ((i-1) / 3) * 3 + ((j-1) / 3) => (i,j) 번째가 위치한 박스 번호
  왼쪽 위 부터 차례대로 0,1,2 .. 8번
  
  
  

문제 풀이

- 실행시간: 448 ms - 메모리: 18504 kb