[백준_2580번] 스도쿠

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

2580번: 스도쿠

[문제]

 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

 

 

나머지 빈 칸을 채우는 방식은 다음과 같다.

 

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

 

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

 

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

 

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

 

[입력 조건]

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

 

[코드]

import java.util.*;

public class BaekJoon_2580 {
	static int[][] map=new int[9][9];
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		
		for(int i=0;i<9;i++)
			for(int j=0;j<9;j++)
				map[i][j]=sc.nextInt();
		
		sudoku(0,0);
	}
	
	// 백트래킹을 사용하여 빈칸에 숫자를 채워넣는 함수
	static void sudoku(int row, int col) {
		if(col==9) { // 한 열이 다 채워졌다면 다음 행으로 넘어간다.
			sudoku(row+1,0);
			return;
		}
		
		if(row==9) { // 모든 행을 다 채웠다면 결과 출력후 종료
			for(int i=0;i<9;i++) {
				for(int j=0;j<9;j++) {
					System.out.print(map[i][j]+" ");
				}
				System.out.println();
			}
			
			System.exit(0);
		}
		
		// 빈칸이라면
		if(map[row][col]==0) {
			// 1~9 사이의 숫자중 한 숫자로 채우기
			for(int i=1;i<=9;i++) {
				// 해당 숫자가 가능한지 탐색
				if(isPossible(row,col,i)) {
					map[row][col]=i;
					sudoku(row,col+1); // 가능하다면 다음 열 탐색
				}	
			}
			map[row][col]=0; // 다음 경우의 수를 위해 값 복구
			return;
		}
		sudoku(row,col+1); // 빈칸이 아니라면 다음 열로 넘어가기
	}
	
	// 채워진 숫자가 가능한지 검사하는 함수
	static boolean isPossible(int row, int col, int num) {
		for(int i=0;i<9;i++) // 같은 숫자가 행에 있다면 불가능
			if(map[row][i]==num)
				return false;
		
		for(int i=0;i<9;i++) // 같은 숫자가 열에 있다면 불가능
			if(map[i][col]==num)
				return false;
		
		int new_row=(row/3)*3; // 3*3 칸의 시작 위치 
		int new_col=(col/3)*3;
		// 3*3 칸에 같은 숫자가 있다면 불가능
		for(int i=new_row;i<new_row+3;i++)
			for(int j=new_col;j<new_col+3;j++)
				if(map[i][j]==num)
					return false;
		
		return true;		
	}
}

 

[고찰] 

 이번 문제는 백트래킹을 사용하여 스도쿠의 빈 칸을 채워나가는 문제였다. 이전에 풀어봤던 N-Queen과 비슷한 문제여서 그리 어렵지 않았다.

 맵을 탐색하면서 빈 칸에 1~9까지의 수 중 가능한 한 수를 채워넣어가다 모든 행, 열을 탐색하면 재귀를 종료하는 방식으로 해결할 수 있었다. 숫자가 가능한지 검사하는 방법이 N-Queen 보다 쉬워서 그런지 N-Queen 문제가 더 어렵게 느껴졌다.