[백준] 2239번 스도쿠 (자바 풀이)
문제
https://www.acmicpc.net/problem/2239
2239번: 스도쿠
스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다
www.acmicpc.net
풀이
꽤 까다로운 DFS+백트래킹 문제였다. 숫자가 행, 열, 3*3 보드에 존재하는지 O(1)에 체크하기 위해
1. HashSet<Integer> row[10]
2. HashSet<Integer> col[10]
3. HashSet<Integer> board[10]
이렇게 3개의 HashSet 배열을 만들었다. 즉, 보드의 (x,y) 좌표에 특정 숫자를 넣으려고 하면, row[x] 와 col[y]에 해당 숫자가 있는지 체크하면 된다. 문제는 3*3 보드에 해당 숫자가 있는지 체크하는게 조금 까다로웠다는 것이다.
나는 3*3 보드의 인덱스를 1~9 까지 위와 같이 나눴다. 맨 왼쪽 위 좌표는 (1,1), 오른쪽 아래는 (9,9)이다.
이걸 일반화해서 구하는 공식을 구하기가 어려웠는데,
(x,y)좌표를 기준으로 3*3보드의 인덱스는 ((x-1)/3+1)*3-2+(y-1)/3 이다.
예를 들어 (4,6)에 특정 숫자를 넣고 싶으면 ((4-1)/3+1)*3-2+(y-1)/3) = 4 이므로 4번째 3*3보드 즉, board[4]에 해당 숫자가 있는지 체크하면 된다. (사실 이렇게 복잡한 방식보다 비트마스킹을 사용하면 더 간단했을 것이다)
아무튼 위와 같은 3개의 HashSet 배열을 이용해서 DFS 탐색을 통해 해당 숫자를 넣을 수 있다면 계속해서 탐색을 진행하면 된다. 숫자를 1부터 9까지 왼쪽 위에서 오른쪽 아래로 탐색하므로 가장 먼저 찾은 정답이 사전 순으로 가장 빠를 수 밖에 없으므로, System.exit(0) 명령으로 종료시켰다.
코드
import java.io.*;
import java.util.*;
public class Baekjoon_2239 {
static int map[][] = new int[10][10];
static HashSet<Integer> row[] = new HashSet[10];
static HashSet<Integer> col[] = new HashSet[10];
static HashSet<Integer> board[] = new HashSet[10];
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
/* 숫자 체크 */
for(int i=1; i<=9; i++) {
row[i] = new HashSet<>();
col[i] = new HashSet<>();
board[i] = new HashSet<>();
}
for(int i=1; i<=9; i++) {
String str = br.readLine();
for(int j=1; j<=9; j++) {
int num = str.charAt(j-1)-'0';
map[i][j] = num;
if(num !=0) {
row[i].add(num);
col[j].add(num);
board[((i-1)/3+1)*3-2+(j-1)/3].add(num);
}
}
}
dfs(1,1);
}
public static void dfs(int x, int y) {
/* 모든 좌표에 원소 넣음 */
if(x >= 9 && y > 9) {
for(int i=1; i<=9 ; i++) {
for(int j=1; j<=9; j++) {
System.out.print(map[i][j]);
}
System.out.println();
}
System.exit(0);
}
/* 가로줄 다 봤으면 아래로 이동 */
if(y>9) {
dfs(x+1,1);
return;
}
/* 0일때만 체크 */
if(map[x][y] == 0){
for(int i=1; i<=9 ; i++) {
if(check(x,y,i)) { // 가로,세로,3*3 보드에 해당 숫자가 없다면
map[x][y] = i;
row[x].add(i);
col[y].add(i);
board[((x-1)/3+1)*3-2+(y-1)/3].add(i);
dfs(x,y+1);
map[x][y] = 0;
row[x].remove(i);
col[y].remove(i);
board[((x-1)/3+1)*3-2+(y-1)/3].remove(i);
}
}
}else { // 아니면 오른쪽으로 한 칸 이동
dfs(x,y+1);
}
}
/* 가로, 세로, 3*3 보드에 해당 숫자가 있는지 체크 */
public static boolean check(int x, int y, int num) {
if(!row[x].contains(num) && !col[y].contains(num) && !board[((x-1)/3+1)*3-2+(y-1)/3].contains(num) ) {
return true;
}
return false;
}
}
결과
