[JAVA] 백준 2580 스도쿠_백트래킹

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

2580번: 스도쿠

 

 접근 : 

 

 - 9X9 2차원 배열 형태의 숫자를 받는다.(board)

 

 - 숫자중 0 이 있으면 빈칸으로 간주하고 해당 하는 곳의 숫자를 탐색한다.

 

 - 숫자를 탐색할 때,  가로 ( ㅡ )한 줄에 중복되는 숫자가 존재하면 안된다.

 

 - 숫자를 탐색할 때, 세로( | ) 한 줄에 중복되는 숫자가 존재하면 안된다.

 

 - 숫자를 탐색할 때, 작은 사각형 (3X3)에 중복되는 숫자가 존재하면 안된다.

 

- (0.0)을 시작점으로 오른쪽 마지막 칸 (0.8) 에 도달하면 (1.0) 다음 줄로 한칸 내려간다.

 

- 마지막 줄, 마지막 칸 (8.8) 으로 내려가면 마지막 숫자를 찾고 더이상 검색을 종료한다.  

 

 

 코드 구현 : 

 

import java.io.*;

public class Main {

	// 놓을 수 있는 경우의 수 탐색
	static class Dfs {
		private int n;
		private int[][] board;
		private boolean is_end;

		public Dfs(int n, int num_of_zero, int[][] board) {
			this.n = n;
			this.board = board;
			this.is_end = false;
			doDfs(0, 0);
		}

		void doDfs(int x, int y) {
			if (x == this.n) {
				doDfs(0, y + 1);
				return;
			}

			// 사각형의 모든 숫자가 채워진 경우
			if (y == this.n) {
				this.is_end = true;
				return;
			}

			if (this.board[y][x] == 0) {
				for (int i = 1; i <= this.n; i++) {
					// 숫자 i 가 가능한지 판단
					if (is_possible(x, y, i)) {
						this.board[y][x] = i;
						doDfs(x + 1, y);
					}
					// 모든 숫자를 다 찾으면 종료
					if (this.is_end) {
						return;
					}
				}
				// 넣은 숫자가 뒤쪽으로 계속 탐색중 아닌게 발견되면 초기화 후 다음 가능한 숫자를 넣은 후 재탐색
				this.board[y][x] = 0;
				return;
			}
			doDfs(x + 1, y);
		}

		boolean is_possible(int x, int y, int num) {
			// ㅡ 방향 중복 검사
			for (int i = 0; i < this.n; i++) {
				if (this.board[y][i] == num) {
					return false;
				}
			}

			// | 방향 중복 검사
			for (int j = 0; j < this.n; j++) {
				if (this.board[j][x] == num) {
					return false;
				}
			}

			int x_idx = x / 3;
			int y_idx = y / 3;
			// 3X3 사각형 중복 검사
			for (int k = y_idx * 3; k < (y_idx + 1) * 3; k++) {
				for (int p = x_idx * 3; p < (x_idx + 1) * 3; p++) {
					// 중복된 숫자가 있다면 false;
					if (this.board[k][p] == num) {
						return false;
					}
				}
			}
			return true;
		}

		public String getResult() {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < this.n; i++) {
				for (int j = 0; j < this.n; j++) {
					sb.append(this.board[i][j]).append(" ");
				}
				sb.append("\n");
			}
			return sb.toString();
		}
	}

	public static void main(String[] srgs) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str_nums;
		int n = 9;
		int[][] board = new int[n][n];
		int temp_num = 0;
		int num_of_zero = 0;
		for (int i = 0; i < n; i++) {
			str_nums = br.readLine().split(" ");
			for (int j = 0; j < n; j++) {
				temp_num = Integer.parseInt(str_nums[j]);
				board[i][j] = temp_num;
			}
		}

		Dfs dfs = new Dfs(n, num_of_zero, board);
		System.out.println(dfs.getResult());
	}
}