[백준] G4 2580번 스도쿠 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

2580번: 스도쿠

[문제] 

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

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

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

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

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

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

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

[입력]

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

[출력]

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

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

 

 

---

[풀이]

1. 0,0부터 탐색을 해서 한 행을 모두 탐색한다. > 행 탐색이 끝나면 다음 행 0열로 돌아감

2. 탐색을 하다가 0인 칸이라면 1~9까지의 수를 넣으면서 유효성 체크를 한다.

3. 만약 유효성 체크를 통과한다면 다음 0을 찾아서 탐색을 한다.

4. 만약 유효성 체크를 통과하지 못한다면, 이전에 잘못된 상태이기 때문에 이전으로 돌아가 해당 위치의 값을 변경해서 다시 체크한다.

5. 이렇게 배열의 모든 값을 탐색하게 된다면 해당 결과를 출력한다.

[접근]

1. DFS + Back Tracking 을 사용해서 문제를 해결하였다.

2. 입력칸이 0인 곳을 찾아서 값을 넣어 유효성 체크를 해보고 참이라면 DFS 탐색을 진행한다.

3. 유효성 체크를 통과하지 못한다면 백트래킹 기법을 이용해 이전으로 돌아가서 다시 탐색을 한다.

[코드]

package BOJ_gold;

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

public class Main_G4_2580 {
	public static int[][] map = new int[9][9]; // 스도쿠 입력을 담을 배열

	public static void main(String[] args) throws Exception {
		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());
			}
		}
		
		dfs(0, 0);
	}

	public static void dfs(int r, int c) {
		// 해당 행을 다 채웠다면 다음 행의 0번째부터 탐색을 해야한다.
		if (c == 9) {
			dfs(r + 1, 0);
			return;
		}

		// 모든 행과 열이 다 채워졌다면 결과를 출력한다.
		if (r == 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);;
		}

		// 현재 위치에 값이 0이라면 빈칸이니까 입력을 해주어야 한다
		if (map[r][c] == 0) {
			// 1~9까지의 수가 들어갈 수 있다.
			for (int i = 1; i < 10; i++) {
				// 입력할려는 값이 들어갈 수 있는지를 체크한다.
				if (check(r, c, i)) { // 가능하다면
					// 해당 위치를 i로 입력해주고
					map[r][c] = i;
					// 다음 탐색을 한다.
					dfs(r, c + 1);
				}
			}
			// 만약 1~9까지의 수를 모두 탐색했는데 불가능 하다면
			// 이전 위치에서 이미 잘못되었다는 것이니까
			// 현재 위치를 0으로 만들고 이전 위치로 돌아간다
			map[r][c] = 0;
			return;
		}
		else { // 해당 위치가 0이 아니라면 이미 값이 입력된 상태니까 다음으로 넘어간다
			dfs(r, c + 1);
		}
	}

	public static boolean check(int r, int c, int num) {
		for (int i = 0; i < 9; i++) {
			// 행에 입력된 값이 있다면
			if (map[r][i] == num) {
				return false;
			}
			
			// 열에 입력된 값이 있다면
			if (map[i][c] == num) {
				return false;
			}
		}

		// 3*3 배열에서의 위치를 구하기 위해 (3으로 나눴을때 몫이 나오면 *3을 하게 되면 해당 위치의 시작)
		int box_r = r / 3;
		int box_c = c / 3;

		// 입력된 곳에서의 3*3 배열을 탐색해서 현재 입력된 값이 있다면 리턴 false
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (map[(box_r * 3) + i][(box_c * 3) + j] == num) {
					return false;
				}
			}
		}

		// 위에서 걸러지는게 없다면 가능한 숫자
		return true;
	}
}