백준 2239번: 스도쿠
문제 설명
- https://www.acmicpc.net/problem/2239
- 스도쿠를 완성해야 합니다.
접근법
- 백트래킹을 활용할 수 있습니다.
- (x,y)위치에서 1,2,3,4,5,6,7,8,9 중 가능한 숫자를 넣어보고 다음 숫자를 채우러 갑니다.
- 스도쿠의 규칙을 벗어나면 다시 되돌아와 다음 숫자를 넣어봅니다.
- 해당 depth에서 가장 처음 만난 빈칸만 확인하고, 나머지 빈칸은 더 깊은 depth에서 확인하면 됩니다.
a b c // a,b,c는 모두 0을 의미하며, depth가 0일 때 -> a의 값만 1,2,3 해보면 됩니다.
1 2 3
2 3 1
1 b c 2 b c 3 b c
1 2 3 1 2 3 2 3 1
2 3 1 2 3 1 2 3 1 // 이렇게 3가지 경우만 고려하면 되지
a 1 c a 2 c a 3 c
1 2 3 1 2 3 2 3 1
2 3 1 2 3 1 2 3 1 // 이러한 경우와(b를 고려)
a b 1 a b 2 a b 3
1 2 3 1 2 3 2 3 1
2 3 1 2 3 1 2 3 1 // 이러한 경우(c를 고려)를 고려할 필요는 없습니다.
유의사항
- 가지치기를 고려하지 않으면 매우 오랜 시간이 걸립니다.
- 빈칸이 N개일 때 각 빈칸에 9개의 숫자를 넣어볼 수 있기 때문에 9^N의 시간이 걸릴 수 있습니다.
- 해당 위치에서 가능한 원소를 직접 list로 return하는 것보다 어떤 원소가 가능한지를 확인하는 게 훨씬 효율적입니다.
- 가로,세로,사각형을 보니깐 여기는 {1,7}이 들어갈 수 있겠군. X
- 1~9까지 넣어보니깐 되는게 1 또는 7이구나. O
- list를 return하는 방식이 어려운 이유는 고려해야 할 사항이 많기 때문입니다.
- 한 예로 가로검사에서 {1,4}, 세로검사에서 {1}, 사각형검사에서 {1,2,3,4,5,6,7,8,9}가 가능하다고 나왔다면 1만 return해야 합니다.
pseudocode
Validate(x,y,c,board){
(x,y)의 가로줄에 c가 있다면 return false;
(x,y)의 세로줄에 c가 있다면 return false;
(x,y)가 포함된 3x3사각형에 c가 있다면 return false;
위 3 조건을 모두 피해왔다면 return true
}
BackT(){
if(모든 빈칸을 규칙에 맞게 다 채웠다면){
정답출력
return;
}
for(i->1~9){ // 가로
for(j->1~9){ // 세로
if(현재 칸에 숫자가 채워져 있다면) continue;
for(c->1~9){
if(Validate(i,j,c,board)){ // 현재의 빈칸을 c로 채울 수 있다면
(i,j)를 c로 채우고
BackT(depth+1,board) // 다음 빈칸을 채우러 갑니다.
현재 (i,j)에서 또 다른 c가 가능한지 확인하기 위해 0으로 리셋시킵니다.
}
}
return false; // depth하나당 하나의 빈칸만 채웁니다.
}
}
}
정답
import java.io.*;
import java.util.*;
public class Main {
static int N = 9;
static int ZeroCnt = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int[][] board = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
char[] temp = st.nextToken().toCharArray();
for (int j = 0; j < N; j++) {
if (temp[j] == '0')
ZeroCnt++;
board[i][j] = temp[j] - '0';
}
}
BackT(0, board);
}
public static boolean Validate(int x, int y, int c, int[][] board) {
for (int i = 0; i < N; i++) { // 가로검사와 세로검사
if (board[x][i] == c) return false;
if (board[i][y] == c) return false;
}
// 사각형 검사
int startX = 3 * (x / 3);
int startY = 3 * (y / 3);
for (int i = startX; i < startX + 3; i++) {
for (int j = startY; j < startY + 3; j++) {
if (board[i][j] == c)
return false;
}
}
return true;
}
public static boolean BackT(int depth, int[][] board) {
if (depth == ZeroCnt) { // 모든 0을 규칙에 맞게 채웠다면
for (int i = 0; i < board.length; i++) {
StringBuffer sb = new StringBuffer();
for (int j = 0; j < N; j++) {
sb.append(board[i][j]);
}
System.out.println(sb.toString());
}
return true;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j] != 0) continue; // 이미 채워진 공간은 고려하지 않습니다.
for (int c = 1; c <= 9; c++) { // 어떠한 빈칸에서 1~9까지 숫자를 고려해 봅니다.
if (Validate(i, j, c, board)) { // 숫자c를 넣었을 때 아무런 이상이 없다면
board[i][j] = c; // c를 넣어봅니다
if (BackT(depth + 1, board)) return true; // 다음 빈칸을 찾으러 갑니다.
board[i][j] = 0; // 가능한 다른c를 넣기 위해 0으로 바꿔줍니다.
}
}
// 처음 만나는 0만 채우고 다른 0은 depth가 더 깊은 곳에서 채우면 되기 때문에 return 합니다.
return false;
}
}
return false;
}
}
Author And Source
이 문제에 관하여(백준 2239번: 스도쿠), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@qwerty1434/백준-2239번-스도쿠저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)