아이디어

• 기본적으로 브루트포스
• 백트래킹을 이용해 가망이 없는 스도쿠 상태로 접근할 수 없도록 해야 시간복잡도를 줄일 수 있다.
• 스도쿠의 게임 규칙을 위반하게 되는 상태가 되면 이전 상태로 되돌아간다.
  • 가로줄, 세로줄, 또는 해당 칸이 위치한 3x3 블록 내에 같은 숫자가 없어야 한다.
  • 이러한 조건은 비트마스킹을 이용하여 더 빠르게 판단할 수 있다.
• 반복 없이 재귀만을 이용해 구성했다. 더 복잡한 것 같지만...
  • 숫자와 함께 체크할 인덱스를 재귀함수로 넘기는 방식
  • 이미 채워져있는 칸에 왔다면 이후 조건을 따지지 않고 다음 칸으로 넘긴다.
  • 인덱스가 81번에 도달하면 스도쿠가 완성된 것이므로 스도쿠판을 출력하고, 종료 플래그를 켜두어 이후 모든 재귀함수가 아무 일도 하지 않도록 하자.
    • 또는 System.exit(0);로 프로그램 자체를 종료시키는 방법도 있다.
  • 숫자가 9보다 커지면 더 이상 유효가 상태가 아니므로 이전 상태로 돌아간다.
• 가망성 체크, 상태 변경과 복귀 부분을 메소드로 따로 구성하여 가독성을 높이자.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	
	static int[][] board = new int[9][9];
	static int[] rowflag = new int[9];
	static int[] colflag = new int[9];
	static int[][] blockflag = new int[3][3];
	static boolean end;
	
	public static void main(String[] args) throws Exception {
		for (int i=0; i<9; i++) {
			char[] line = rd.readLine().toCharArray();
			for (int j=0; j<9; j++) {
				set(i, j, line[j] - '0');
			}
		}

		bfs(0, 1);
	}
	
	static boolean check(int i, int j, int n) {
		if ((rowflag[i] >> n & 1) == 1) return false;
		if ((colflag[j] >> n & 1) == 1) return false;
		if ((blockflag[i/3][j/3] >> n & 1) == 1) return false;
		return true;
	}
	
	static void bfs(int idx, int n) {
		if (end) return;
		if (idx == 81) {
			print();
			end = true;
			return;
		}
		if (n == 10) return;
		
		int y = idx / 9;
		int x = idx % 9;
		
		if (board[y][x] != 0) {	// by-pass
			bfs(idx + 1, n);
			return;
		}
		if (check(y, x, n)) {
			set(y, x, n);
			bfs(idx + 1, 1);
		}
		reset(y, x);
		bfs(idx, n + 1);
	}
	
	static void print() {
		for (int i=0; i<9; i++) {
			for (int j=0; j<9; j++) {
				sb.append(board[i][j]);
			}
			sb.append('\n');
		}
		System.out.println(sb);
	}
	
	static void set(int y, int x, int n) {
		board[y][x] = n;
		rowflag[y] |= 1 << board[y][x];
		colflag[x] |= 1 << board[y][x];
		blockflag[y/3][x/3] |= 1 << board[y][x];
	}
	
	static void reset(int y, int x) {
		rowflag[y] &= ~(1 << board[y][x]);
		colflag[x] &= ~(1 << board[y][x]);
		blockflag[y/3][x/3] &= ~(1 << board[y][x]);
		board[y][x] = 0;
	}
}

메모리 및 시간

• 메모리: 17220 KB
• 시간: 756 ms

리뷰

• 구현 문제에는 코드의 구조화만 잘 하면 쉽게 풀 수 있다.
• (23. 11. 15. 수정) bfs가 아니라 dfs인데 이름을 잘못 썼다.