[#알고리즘/백트래킹/[백준]2580번: 스도쿠(java)]

📘 Question

💡 Solution

백트래킹 기법을 사용하였다. (0, 0)에서부터 (9, 9)까지 탐색하여 빈칸이 아니면 다음 칸으로 옮겨 다시 탐색하고, 빈칸이라면 알맞은 값을 찾는 check 함수를 수행한다. 이때, 예를 들어 하나의 빈칸에 5를 채운 후 다음 빈칸으로 옮겨갔을 때 맞는 값이 없다면 그것은 5를 채울 때부터 값이 잘못 채워졌음을 의미한다. 따라서 5로 채웠던 칸을 다시 빈칸으로 만들어주는 작업이 필요하다.

check 함수는 value를 인자로 받으면 1. 빈칸과 같은 행, 2. 빈칸과 같은 열, 3. 빈칸이 포함된 3*3 칸 이 세 공간에 value와 겹치는 원소가 있는지 확인한다. 겹치지 않는 value를 찾아 해당 값을 빈칸에 채운다.

💡 Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_2580 {
	static int[][] map = new int[9][9];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		for(int i = 0; i < 9; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j = 0; j < 9; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		sudoku(0, 0);
	}
	
	//(0, 0)부터 (9, 9)까지 탐색
	public static void sudoku(int row, int col) {
		// 열이 9이면 다음 행으로 이동하여 탐색 
		if(col == 9) {
			sudoku(row + 1, 0);
			return;
		}
		
		// 모든 행에 대해 sudoku를 수행하면 출력 후 종료
		if(row == 9) {
			StringBuilder sb = new StringBuilder();
			for(int i = 0; i < 9; i++) {
				for(int j= 0; j < 9; j++) {
					sb.append(map[i][j]).append(' ');
				}
				sb.append('\n');
			}
			System.out.println(sb);
			System.exit(0);
		}
		
		// 해당 칸이 빈칸이면 1부터 9 중 어떤 값이 들어갈 수 있는지 check 
		if(map[row][col] == 0) {
			for(int i = 1; i <= 9; i++) {
				// i를 빈칸에 넣을 수 있다면
				if(check(row, col, i)) {
					map[row][col] = i;
					sudoku(row, col + 1);
				}
			}
			map[row][col] = 0;
			return;
		}
		
		sudoku(row, col + 1);
	}
	
	// 어떤 값이 빈칸에 들어갈 수 있는지를 확인.
	public static boolean check(int row, int col, int value) {
		// 같은 행에 겹치는 원소가 있는지 확인.
		for(int i = 0; i < 9; i++) {
			if(map[row][i] == value) {
				return false;	
			}
		}
		
		// 같은 열에 겹치는 원소가 있는지 확인.
		for(int i = 0; i < 9; i++) {
			if(map[i][col] == value) {
				return false;
			}
		}
		
		// 3*3 칸 안에 겹치는 원소가 있는지 확인.
		int dr = (row / 3) * 3;
		int dc = (col / 3) * 3;
		
		for(int i = dr; i < dr + 3; i++) {
			for(int j = dc; j < dc + 3; j++) {
				if(map[i][j] == value) {
					return false;
				}
			}
		}
		
		// 겹치는 원소가 없을 경우
		return true;
	}

}