백준 2580번
https://www.acmicpc.net/problem/2580
문제
게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.
생각하기
2차원 배열에서 행, 열을 탐색하는 과정 자체가 백트래킹의 대표에제인 N-Queen과 굉장히 유사한 문제였던 것 같다.
N-Queen을 풀어보긴 했지만, 혼자 힘으로 해결한게 아니어서 그런지 이 문제도 몇시간을 고민하고 나서 결국 다른 분들의 코드를 보고 해결 할 수 있었다.
동작
2차원 배열을 스도쿠 형식으로 생성하고 난 후 부터 시작한다.
sdoku메소드를 재귀를 통해 실행해서 배열을 전체 탐색한다.
// 열이 9일경우 다음 줄로 넘어가기위해 행을 1증가시킴.
if(y == 9) {
sdoku(x + 1, 0);
return;
}
// 행이 9에 도달해서 마지막 줄 까지 왔을 때, 종료
if(x == 9) {
StringBuilder sb = new StringBuilder();
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
sb.append(arr[i][j]).append(' ');
}
sb.append('\n');
}
System.out.println(sb);
System.exit(0);
}위 2가지는 재귀에서 탈출을 하는 2가지 조건인데
if(y == 9) { 는 y가 9일 때, 다음 행으로 넘기기 위한 줄바꿈이 필요하다는 것을 알리기위한 조건문이다.
if(x == 9) {는 x가 9일 때, 모든 스도쿠배열을 탐색을 마쳤으므로 출력하고 종료하는 조건문이다.
// 스도쿠배열에서 빈칸인 0을 만났을 때,
if(arr[x][y] == 0) {
for(int i=1; i<=N; i++) {
if(check(x, y, i)) {
arr[x][y] = i;
sdoku(x, y + 1);
}
}
arr[x][y] = 0;
return;
}
sdoku(x, y + 1);해당 부분은 빈칸인 0을 만났을 때 이다.
arr이 0일 때 빈칸을 만나면 check메소드를 실행하게 되는데,
여기서 우리가 스도쿠에서 빈칸에 알맞은 숫자를 채우기 위한 방법은 1~9까지의 숫자를 모두 대입해보는 방식이다.
static boolean check(int x, int y, int value) {
for(int i=0; i<N; i++) {
if(arr[x][i] == value) {
return false;
}
}
for(int i=0; i<N; i++) {
if(arr[i][y] == value) {
return false;
}
}
int setX = (x/3) * 3;
int setY = (y/3) * 3;
for(int i=setX; i<setX + 3; i++) {
for(int j=setY; j<setY + 3; j++) {
if(arr[i][j] == value) {
return false;
}
}
}
return true;check함수는 내가 넣으려는 숫자가 스도쿠의 조건에 부합해서 넣을 수 있는 숫자인지를 검사하는 메소드이다.
1~9까지의 숫자를 check의 매개변수인 value에 넣어서 전체 조건을 검사한다.
- 첫 번째 조건은
if(arr[x][i] == value) {으로 행에서 이value와 겹치는 숫자가 있는지 검사한다. - 두 번째 조건은
if(arr[i][y] == value) {열에서value와 겹치는 숫자가 있는지 검사한다. - 세 번째 조건은
int setX = (x/3) * 3;
int setY = (y/3) * 3;` x와 y의 값을 통해 작은 3x3 배열에서 겹치는 숫자가 있는지 검사하는 것이다.
이 3가지 조건을 모두 통과하면 true를 반환하게 된다.
// 스도쿠배열에서 빈칸인 0을 만났을 때,
if(arr[x][y] == 0) {
for(int i=1; i<=N; i++) {
if(check(x, y, i)) {
arr[x][y] = i;
sdoku(x, y + 1);
}
}
arr[x][y] = 0;
return;
}
sdoku(x, y + 1);이후 다시 check가 true를 받았을 경우로 돌아오면,
i가 적합한 것을 알게되고 arr[x][y] 의 값을 i로 갱신해주고 다음 열로 넘어가기 위해 sdoku메소드를 재귀 실행한다.
코드
Java
import java.util.*; import java.io.*; public class Main { static int N = 9; static int arr[][] = new int[N][N]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); for(int i=0; i<N; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); for(int j=0; j<N; j++) { arr[i][j] = Integer.parseInt(st.nextToken()); } } sdoku(0, 0); } // End of main static void sdoku(int x, int y) { // 열이 9일경우 다음 줄로 넘어가기위해 행을 1증가시킴. if(y == 9) { sdoku(x + 1, 0); return; } // 행이 9에 도달해서 마지막 줄 까지 왔을 때, 종료 if(x == 9) { StringBuilder sb = new StringBuilder(); for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { sb.append(arr[i][j]).append(' '); } sb.append('\n'); } System.out.println(sb); System.exit(0); } // 스도쿠배열에서 빈칸인 0을 만났을 때, if(arr[x][y] == 0) { for(int i=1; i<=N; i++) { if(check(x, y, i)) { arr[x][y] = i; sdoku(x, y + 1); } } arr[x][y] = 0; return; } sdoku(x, y + 1); } // End of DFS static boolean check(int x, int y, int value) { for(int i=0; i<N; i++) { if(arr[x][i] == value) { return false; } } for(int i=0; i<N; i++) { if(arr[i][y] == value) { return false; } } int setX = (x/3) * 3; int setY = (y/3) * 3; for(int i=setX; i<setX + 3; i++) { for(int j=setY; j<setY + 3; j++) { if(arr[i][j] == value) { return false; } } } return true; } // End of check } // End of Main class
Kotlin
import java.util.*; import java.io.*; private val N = 9; private val arr = Array(N){Array(N){0}} fun main() { val br = BufferedReader( InputStreamReader(System.`in`) ) for(i in 0 until N) { var st = StringTokenizer(br.readLine()) for(j in 0 until N) { arr[i][j] = st.nextToken().toInt() } } sdoku(0, 0) } // End of main fun sdoku(x : Int, y : Int) { // 열이 9일 경우 다음행으로 넘어감 (줄바꿈) if(y == N) { sdoku(x + 1, 0); return; } // 행이 9가 됬을 경우, 모든 탐색 완료 종료. if(x == N) { val sb = StringBuilder(); for(i in 0 until N) { for(j in 0 until N) { sb.append(arr[i][j]).append(' ') } sb.append('\n') } println(sb) System.exit(0); } // 스도쿠 배열에서 빈칸을 만났을 때, if(arr[x][y] == 0) { // 1 ~ 9까지 모든 숫자를 대입해보면서 조건에 맞는 숫자를 찾음 for(i in 1 until 10) { // 조건이 true일 경우, 빈칸에 해당 숫자를 넣고 // 다음 줄로 넘어감. if(check(x, y, i)) { arr[x][y] = i; sdoku(x, y + 1); } } arr[x][y] = 0; return; } sdoku(x, y + 1); } // End of sdoku fun check(x : Int , y : Int, value : Int) : Boolean { // 열에 value가 있으면, false를 반환 for(i in 0 until N) { if(arr[x][i] == value) { return false; } } // 행도 검사해서 value가 있으면 false 처리 for(i in 0 until N) { if(arr[i][y] == value) { return false; } } // x, y를 기준으로 3*3 배열의 시작점을 찾음 val setX = (x / 3) * 3; val setY = (y / 3) * 3; // 3*3 배열에서 value와 겹치는 숫자가 있는지 검사 for(i in setX until setX+3) { for(j in setY until setY+3) { if(arr[i][j] == value) { return false; } } } // 모든 조건 통과 하면 true를 반환 return true; } // End of check
