https://www.acmicpc.net/problem/2239
2239번: 스도쿠
스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다
www.acmicpc.net
문제 설명
스도쿠 퍼즐이 주어지면, 스도쿠의 규칙에 맞게 빈칸을 채워서 그 결과 값을 출력하는 문제입니다.
스도쿠의 규칙은 문제에도 나온 것처럼, 각 행과, 열, 3*3 보드 내에서 1~9까지의 숫자가 중복 없이 나타나야 한다는 것입니다.
또한 출력 조건으로 답이 여러 개라면 사전순으로 가장 빠른 정답을 출력하라는 조건이 있습니다.
정리하자면 스도쿠의 조건을 만족시키는 사전순으로 가장 빠른 정답을 찾아내는 것이 문제에서 요구하는 것입니다.
문제 접근
저는 문제를 풀기에 앞서서, 3가지 고민이 들었습니다.
첫 번째로, 스도쿠의 조건을 어떻게 체크를 할까?
두 번째로, 사전순으로 가장 빠른 답은 어떤 것일까?
세 번째로, 각 빈칸에 수를 어떤 식으로 넣어서, 스도쿠 규칙과 사전순으로 빠른 것을 구할 수 있을까?
위의 고민에서 가장 먼저 생각나는 방법은 완전탐색을 이용하는 방법이었습니다. 도저히 각 칸에 즉시 알맞은 수를 넣는 방법을 떠올리지 못했기 때문입니다. 스도쿠 판 전체가 빈칸으로 주어진다고 했을 때, 완전탐색을 통해 각 칸을 채운다고 해도 9*9 (스도쿠 판의 크기) * 9(들어갈 수 있는 수) 보다는 적겠다고 생각했고, 완전탐색을 진행해도 시간적으로 가능하다고 생각했습니다. 그렇게 세 번째 고민은, 완전탐색을 이용한 방향으로 접근하겠다고 생각했습니다.
두 번째 고민은, 완전탐색에 대해서 생각하고 나니 쉽게 생각이 났습니다. 주어진 빈칸들에 수를 집어넣을 때, 행과 열이 작은 순서대로 (왼쪽 상단 -> 오른쪽 하단) 수를 주고, 각 빈칸은 1부터 9까지 증가하면서 대입을 해서 스도쿠의 정답을 찾는다면, 사전순으로 가장 빠른 스도쿠 정답이 나올 수 있다고 생각이 들었습니다.
마지막으로 스도쿠의 조건을 체크하는 방법으로는 스도쿠 조건(행, 열, 3*3 내에 중복 X)을 전부 반복문으로 체크하는 방법이 생각났습니다. 앞서서 완전탐색을 이용했을 때, 경우의 수가 9*9*9보다 적을 것이라고 생각했기 때문에, 27이 곱해지는 정도는 제한시간인 2초 이내에 충분히 가능하다고 생각이 들었습니다.
하지만, 매번 반복문을 도는 것은, 비효율적일 수 있다고 생각해서, 각 행, 열, 3*3 구간에 특정 숫자가 있는지 체크하는 boolean 배열을 만든다면 숫자에 대해서 탐색을 할 때, O(N)에서 O(1)로 줄일 수 있다고 생각했고, 더 효율적일 수 있다고 생각했습니다.
문제 풀이
변수 설명
사용된 변수는 아래 4개와 빈칸(0)의 좌표를 체크하기 위해 Pos라는 클래스를 제작했습니다.
static int[][] matrix; // 스도쿠 판
static boolean [][][] check; // 검증을 위한 3차원 배열
static List<Pos> next; // 빈 칸을 저장하는 리스트
static boolean flag; // 탐색이 완료된 경우를 표시하는 변수
static class Pos{
int r;
int c;
public Pos(int r, int c) {
this.r = r;
this.c = c;
}
}
변수 설정
변수를 입력받을 땐, 행과 열이 작은 순서대로 입력을 받았습니다. 이 과정에서 빈칸이 아닌 수가 입력이 되었을 때, 해당 행, 열, 구간에 그 수가 존재한다는 것을 체크해 주었습니다. 빈칸(0)이 나온 경우엔, next라는 이름의 list에 해당 좌표를 저장을 해주었습니다.
// 변수 설정
private static void setVariables() throws IOException {
matrix = new int[9][9];
check = new boolean[3][9][10];
next = new ArrayList<>();
for (int i = 0; i < 9; i++) {
String line = br.readLine();
for (int j = 0; j < 9; j++) {
int number = line.charAt(j) - '0';
matrix[i][j] = number;
if (number != 0) { // 0이 아니라면, check 배열에 true로 표현한다.
check[0][i][number] = true; // i번째 행에 number가 있다.
check[1][j][number] = true; // j 번째 열에 number가 있다.
check[2][getSection(i,j)][number] = true; // 해당 구역에 number가 있다.
}else{
next.add(new Pos(i,j)); // 0이 주어진 좌표 저장
}
}
}
}
구역 설정
아래 함수는 해당 좌표가 몇번째 3*3 좌표에 속하는지를 계산합니다.
// section 구하기
/* 아래 그림처럼 나눈다.
0 1 2
3 4 5
6 7 8
*/
private static int getSection(int r, int c){
int row = r/3;
int col = c/3;
return row * 3 + col;
}
수 검증
완전탐색 과정에서 현재 좌표에 입력된 수가 가능한지에 대해서 체크합니다.
// 현재 입력하는 숫자가 가능한 숫자인지 체크
//(가로 라인에서 그 수가 있는지, 세로 라인에서 그 수가 있는지, 3*3 칸에서 그 수가 있는지)
private static boolean isValid(int r, int c, int num) {
return !(check[0][r][num] || check[1][c][num] || check[2][getSection(r,c)][num]);
}
완전탐색
완전탐색 코드입니다. 입력에서 주어진 빈칸의 0번 인덱스부터 마지막 인덱스까지 1부터 9까지의 수를 넣을 수 있는지 검증하고, 가능하다면 해당 수를 넣어보면서 정답을 찾습니다. 빈칸의 좌표가 (0,0) -> (8,8) 순으로 리스트에 들어있고, 각 좌표는 1->9로 증가하는 순서대로 수를 대입하기 때문에, 처음으로 탐색에 성공한 결과가 사전식으로 가장 앞서는 결과임을 보장합니다.
// 완전 탐색
private static void bf(int index){
if (index == next.size()) {
flag = true;
appendResult();
return;
}
Pos pos = next.get(index);
for (int i = 1; i <= 9 ; i++) {
if (isValid(pos.r, pos.c, i)) {
matrix[pos.r][pos.c] = i;
// 현재 좌표에 배치한 수를 체크 배열에 저장
check[0][pos.r][i] = true;
check[1][pos.c][i] = true;
check[2][getSection(pos.r,pos.c)][i] = true;
bf(index+1);
if(flag) return;
// 재귀가 끝나면, 배열들 다시 원복
matrix[pos.r][pos.c] = 0;
check[0][pos.r][i] = false;
check[1][pos.c][i] = false;
check[2][getSection(pos.r,pos.c)][i] = false;
}
}
}
결과
주로 시간이 빠른 사람들의 코드를 보면 체크 배열을 이용한 경우가 많아, 그 방법을 생각해 낸 것이 좋았다고 생각합니다. 조금 더 느린 풀이들도 있는 것을 보니, 체크 배열을 이용하지 않고, 반복문으로 해당 수를 검증하는 방법 역시 문제를 푸는데 무리는 없었던 것 같습니다.
전체 코드
http://boj.kr/dea7592ea63149cf83c000d17bbe80e6
공유 소스 보기
www.acmicpc.net
