문제

스도쿠 - 2580

---

문제 이해

일반적으로 아는 스도쿠 문제를 해결한다.

• 9X9 스도쿠 문제를 해결
• 가로, 세로, 3X3에 1~9의 수가 하나씩 들어가야 한다.
• DFS, Back Tracking을 이용해서 문제를 해결한다.

---

코드

/* baekjoon 2580 */

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

public class Sudoku {
  static final int SUDOKU_SIZE = 9; // 스도쿠 사이즈
  static int[][] problem; // 해결해야할 스도쿠

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    // 스도쿠 문제 입력 시작
    problem = new int[SUDOKU_SIZE][SUDOKU_SIZE];

    for (int i = 0; i < SUDOKU_SIZE; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      for (int j = 0; j < SUDOKU_SIZE; j++) {
        problem[i][j] = Integer.parseInt(st.nextToken());
      }
    }
	// 스도쿠 문제 입력 완료
    
    // 0,0 부터 탐색 시작
    solution(0, 0);
  }

  // 2d Array 출력 함수
  public static void print(int[][] matrix) {
    for (int i = 0; i < SUDOKU_SIZE; i++) {
      for (int j = 0; j < SUDOKU_SIZE; j++) {
        System.out.print(problem[i][j] + " ");
      }
      System.out.println();
    }
  }

  // DFS + Back Tracking
  public static void solution(int r, int c) {
    // 가로 방향으로 다 찾으면 세로 방향으로 찾기
    if (c == SUDOKU_SIZE) {
      solution(r + 1, 0);
      return;
    }

    // 세로방향 다 찾으면 완전히 종료
    if (r == SUDOKU_SIZE) {
      print(problem);
      System.exit(0);
    }

    if (problem[r][c] == 0) {
      for (int i = 1; i <= SUDOKU_SIZE; i++) { 
        // 1~9 까지 넣어보면서 넣어도 되는지 확인
        if (squardCheck(r, c, i, problem) && verticalCheck(c, i, problem) && horizontalCheck(i, problem[r])) {
          problem[r][c] = i;
          // 가로방향 먼저 탐색
          solution(r, c + 1);
        }
      }
      // [r][c] 0으로 초기화(Back Tracking)
      problem[r][c] = 0;
      return;
    }
    // 0이 아니면 다음 가로 방향 확인
    solution(r, c + 1);
  }

  // 사각형 확인
  public static boolean squardCheck(int r, int c, int v, int[][] matrix) {
    int startR = (r / 3) * 3;
    int endR = startR + 3;
    int startC = (c / 3) * 3;
    int endC = startC + 3;

    for (int i = startR; i < endR; i++) {
      for (int j = startC; j < endC; j++) {
        if (matrix[i][j] == v) {
          return false;
        }
      }
    }

    return true;
  }

  // 세로 확인
  public static boolean verticalCheck(int c, int v, int[][] matrix) {
    for (int i = 0; i < SUDOKU_SIZE; i++) {
      if (matrix[i][c] == v)
        return false;
    }
    return true;
  }

  // 가로 확인
  public static boolean horizontalCheck(int v, int[] matrix) {
    for (int i = 0; i < SUDOKU_SIZE; i++) {
      if (matrix[i] == v)
        return false;
    }

    return true;
  }
}

---

코드 설명

1. 스도쿠를 입력받는다.
2. 0,0 부터 탐색을 한다.
3. 스도쿠의 현재 위치의 값이 0이라면 1~9에서 하나씩 넣어가면서 넣을 수 있는지 확인한다.
4. 확인 작업
   4-1. 만약 넣을 수 있다면
   4-1-1. 해당 위치의 스도쿠 값을 변경한다.
   4-1-2. 재귀호출을 하는데 먼저 가로방향으로 탐색하기 위해 col + 1 방향으로 0을 찾는다.
   4-1-3. 깊게 값들을 설정하다보면 안 맞을 수 있으니 Back-Tracking 기법을 사용한다.
   4-1-4. 변경해줬던 값을 초기화
   4-2. 만약 넣을 수 없다면 다음 가로방향(col + 1)을 탐색한다.
5. 가로 방향으로 탐색하다 보면 가로 끝에 도달하게 된다. 이때부터는 세로 방향으로 탐색을 진행하며 값들을 바꿔준다.
6. 세로 방향의 값이 스도쿠 크기만큼 된다면 모든 행과 열을 탐색한 것이므로 종료를 시켜준다.

---