[백준 2580] 스도쿠(Java)

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이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

출력

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

제한

• baekjoon의 백트래킹 알고리즘으로 풀 수 있는 입력만 주어진다. 다음은 그 알고리즘의 수행 시간이다.
  • C++14: 80ms
  • Java: 292ms
  • PyPy3: 1172ms

풀이 설명

1. 스도쿠 전체를 탐색하며 빈칸을 찾아 1~9까지 넣어보는 함수 dfs를 선언한다.

2. dfs의 매개변수로 현재 칸의 행과 열 인덱스인 x, y를 넘겨준다. 처음 시작은 0, 0이다.

3. 열 인덱스가 9가 되면 다음 행의 0열부터 다시 체크하도록 dfs함수를 재귀호출한다.

4. 행 인덱스도 9가 되면 모든 칸을 다 체크했다는 의미이므로, 스도쿠 전체를 출력하고 main함수를 끝낸다.

   여기서 main을 끝내지 않으면 이후 다른 답이 나왔을 때 스도쿠 전체가 또 출력이 되어 버린다. 아예 끝내버려야 한다.

5. 위 조건을 만족하지 않고 현재 칸이 빈칸이라면(0이라면), 1~9까지의 숫자를 하나씩 다 넣어볼 것이다.

  5-1. 1~9까지 각 숫자가 check함수를 만족한다면(가로 세로 같은 영역에 없다면) map의 현재 칸을 그 숫자로 바꾸고,          dfs함수를 열 인덱스만 하나 올려서 재귀호출한다.

  5-2. 숫자를 다 넣어봤다면 map의 현재 칸을 다시 0으로 바꾸고 현재 dfs 함수를 끝낸다.

        (0으로 다시 바꾸어야 이전 dfs에서의 남은 연산에 영향을 끼치지 않는다.)

6. 현재 칸이 빈 칸이 아니어도 dfs함수에 열 인덱스+1을 넘겨 재귀호출한다.

Java 코드

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

public class Main {

	static int N = 9;
	static int[][] map;
	static boolean[][] fulled;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		map = new int[N][N];
		
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		dfs(0, 0);
	}
	
	public static void dfs(int x, int y) {
		if(y == N) {
			dfs(x+1, 0);
			return;
		}
		
		if(x == N) {
			StringBuilder sb = new StringBuilder();
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					sb.append(map[i][j]).append(" ");
				}
				sb.append("\n");
			}
			System.out.println(sb);
			System.exit(0);
		}
		
		if(map[x][y] == 0) { //현재 스도쿠 위치가 빈칸이라면
			for(int num = 1; num <= N; num++) { //빈 칸에 1~9까지 넣어볼것임
				if(check(x, y, num)) { //가로 세로 같은 9칸에 num이 없으면
					map[x][y] = num;
					dfs(x, y+1);
				}
			}
			map[x][y] = 0;
			return;
		}
		
		dfs(x, y+1);
	}

	public static boolean check(int x, int y, int n) {
		for(int i=0; i<N; i++) {
			if(map[x][i] == n) return false; //가로에 있으면 false
			if(map[i][y] == n) return false; //세로에 있으면 false
		}

		for(int i=(x/3)*3; i<(x/3)*3+3; i++) {
			for(int j=(y/3)*3; j<(y/3)*3+3; j++) {
				if(map[i][j] == n) return false; //같은 칸에 있으면 false
			}
		}
		return true;
	}
}