[백준] 2239번 스도쿠 (자바 풀이)

문제

https://www.acmicpc.net/problem/2239

2239번: 스도쿠

 

풀이

꽤 까다로운 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 보드에 해당 숫자가 있는지 체크하는게 조금 까다로웠다는 것이다.

[그림 1] 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;
	}

}

 

결과