122. 2580(스도쿠)

import java.util.*;
import java.io.*;

class Main {
	static int[][] sudoku;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		sudoku = new int[9][9];

		for (int i = 0; i < 9; i++) {
			String[] sBits = br.readLine().split(" ");
			for (int j = 0; j < 9; j++) {
				sudoku[i][j] = Integer.parseInt(sBits[j]);
			}
		}

		DFS(0, 0);
		
		
	}

	public static boolean search(int row, int col, int value) {
		for (int i = 0; i < 9; i++) {
			if (sudoku[row][i] == value) {
				return false;
			}
		}

		for (int i = 0; i < 9; i++) {
			if (sudoku[i][col] == value) {
				return false;
			}
		}

		int rowFirst = (row / 3) * 3;
		int colFirst = (col / 3) * 3;

		for (int i = rowFirst; i < rowFirst + 3; i++) {
			for (int j = colFirst; j < colFirst + 3; j++) {
				if (sudoku[i][j] == value) {
					return false;
				}
			}
		}

		return true;
	}

	public static void DFS(int row, int col) {
		if (col == 9) {
			DFS(row + 1, 0);
			return;
		}

		if (row == 9) {
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					sb.append(sudoku[i][j]).append(" ");
				}
				sb.append("\n");
			}
			System.out.print(sb);
			System.exit(0);
		}

		if (sudoku[row][col] == 0) {
			for (int i = 1; i <= 9; i++) {
				if (search(row, col, i)) {
					sudoku[row][col] = i;
					DFS(row, col + 1);
				}
			}
			sudoku[row][col] = 0;
			return;
		}

		DFS(row, col + 1);
	}
}

문제요약

스도쿠가 주어졌을 때 백트래킹을 이용하여 해결해보시오

설명

사실 차근차근해보면 문제가 크게 어렵지 않다.

아래 판이 주어지면 위와같이 만들면 된다.

 

스도쿠를 해결하는 단계는 다음과 같다.

---

search

1. 행에서 열의 요소를 탐색한다.

public static boolean search(int row, int col, int value) {
    // 1. 행에서 열을 탐색함
		for (int i = 0; i < 9; i++) {
			if (sudoku[row][i] == value) {
				return false;
			}
		}
        return true;
      }

2. 열에서 행의 요소를 탐색한다.

public static boolean search(int row, int col, int value) {
	// 2.열에서 행을 탐색함
    	for (int i = 0; i < 9; i++) {
			if (sudoku[i][col] == value) {
				return false;
			}
		}
        return true;
        }

3. 작은 사각형 탐색

public static boolean search(int row, int col, int value) {
	// 3.작은 사각형 탐색
 		int rowFirst = (row / 3) * 3;
		int colFirst = (col / 3) * 3;

		for (int i = rowFirst; i < rowFirst + 3; i++) {
			for (int j = colFirst; j < colFirst + 3; j++) {
				if (sudoku[i][j] == value) {
					return false;
				}
			}
		}

		return true;
	}

작은 삼각형의 첫위치는 rowFirst와 colFirst를 통해 정해준다.

 

 

위와같이 3가지의 경우를 search 하여 만약 하나라도 조건에 부합하다면 False (그 값이 아님) 를 반환하고 전부 통과한다면(그 값이 맞음) True를 반환한다.

public static boolean search(int row, int col, int value) {
		for (int i = 0; i < 9; i++) {
			if (sudoku[row][i] == value) {
				return false;
			}
		}

		for (int i = 0; i < 9; i++) {
			if (sudoku[i][col] == value) {
				return false;
			}
		}

		int rowFirst = (row / 3) * 3;
		int colFirst = (col / 3) * 3;

		for (int i = rowFirst; i < rowFirst + 3; i++) {
			for (int j = colFirst; j < colFirst + 3; j++) {
				if (sudoku[i][j] == value) {
					return false;
				}
			}
		}

		return true;
	}

 

---

DFS

Search를 구현했으면 다음에는 깊이 우선 탐색을 통해 하나하나 비교해 나간다.

 

public static void DFS(int row, int col) {
	//열이 9일 경우 행을 1증가 시키고 열은 0으로 초기화
		if (col == 9) {
			DFS(row + 1, 0);
			return;
		}
		
        // 행이 9일 경우 모든 곳을 탐색한 것임.
		if (row == 9) {
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					sb.append(sudoku[i][j]).append(" ");
				}
				sb.append("\n");
			}
			System.out.print(sb);
			System.exit(0);
		}

열의 수가 9에 도달한다면 열은 탐색이 끝난것이다.

따라서 행을 1증가시켜주고 열을 0으로 초기화 해서 1행을 탐색하기 시작한다.

 

행까지 9가 된다면 모든 위치를 탐색을 마친것으로 결과값을 출력하고 exit를 통해서 프로그램을 종료해준다.

 

// 0인 녀석을 만났을 경우
if (sudoku[row][col] == 0) {
			// 값은 1~9 나올 수 있음
			for (int i = 1; i <= 9; i++) {
				if (search(row, col, i)) {
					sudoku[row][col] = i;
					DFS(row, col + 1);
				}
			}
            // for을 다 돌렸지만 부합할 경우
			sudoku[row][col] = 0;
			return;
		}

		DFS(row, col + 1);
	}

0인 녀석이 나왔을 경우 (0이 빈칸이다.) 탐색을 시작해야한다.

숫자는 1~9까지 나올 것이다.

따라서 1~9를 반복문을 통해 반복을 해준다.

search를 통해 행,열,값을 넘겨주고, 만약 search 함수에서 모든 결과에 부합(일치하는 수가 없다) 그 수는 정답이므로 sudoku에 저장해준다.

 

해당 위치는 작업이 끝났으므로 열을 +1하여 다음 위치로 넘어간다.

 

sudoku[row][col] = 0;
	return;

이 구문은 0인 녀어석을 만났지만 1~9가 모두 부합할 수도 있다.

그 경우에 0인 녀어석을 다시 0으로 초기화 해주어야 한다.

 

DFS(row, col + 1);

마지막으로  0이 아닌경우 다음 열로 넘어가 탐색을 시작한다.