[백준 자바 2239] 스도쿠 (골드 4)

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

2239번: 스도쿠

 

전체코드 이미지. 텍스트는 맨 아래에 있다.

 

---

 

 

처음에 어떻게 풀지 하다가 그래도 구글링 하기 전까지 50%는 다 풀어놨었다 좀 더 시간 들였으면 다 풀었을 텐데 아쉽 

 

일단 1. 백트래킹 +  2. 가로, 세로, 3*3칸 체크하기. 이 2개가 큰 흐름이고 여기까진 알았다. 근데 난 구현이 약한가보다 

 

문제 푸는 순서는 다음과 같다. 

1. 9*9칸의 보드판을 2차원 배열에 입력받고
2. 그 중 0인 칸을 따로 모아둔 후
3. 백트래킹으로 0인 칸을 전부 돌면서 
4. 각 0인 칸에 1~9까지 숫자 충돌여부를 체크하고 
5. 이상 없으면 계속 대입해나가며
6. 전부 대입하면 처음 만들어지는 스도쿠를 출력 후 종료 

 

board 는 스도쿠 판을 입력받는 2차원 9*9 배열이고, 

zeroLsit는 0인 칸의 n, m 좌표를 가지는 리스트이다.

 

이중 반복문은 입력을 받아 board 의 각 좌표에 입력값을 넣어주며, 

만약 그 값이 0이면 따로 zeroList에 모아둔다. 

 

이렇게 순서대로 모아둬야 출력의 조건인 사전순으로 출력할 수 있다. 

 

마지막으로 백트래킹으로 첫 번째 0인 칸을 입력하여 실행한다. 

 

 

---

 

 

처음에는 종료조건으로 0인 칸을 전부 돌았다면, 여기까지 오면서 스도쿠가 만들어지는지 체크를 해와서 이상없는 완전한 스도쿠가 만들어졌으며, 또한 처음으로 만들어지는 스도쿠이므로 사전순으로도 정렬된 상태다. 

따라서 이를 출력하고, 하나만 출력하면 되므로 프로그램을 종료시킨다. 

 

종료조건이 아니라면 현재 0인 칸의 n행 m열을 가져오고, 

그 칸에 1부터 9칸까지 대입했을 때 스도쿠에 이상이 없는지 isRight 함수로 체크한 후 

이상이 없다면 대입하고 다음 0인 칸을 처리하기 위해 백트래킹을 돌린다. 

 

만약 백트래킹이 다시 return으로 돌아왔다는 것은 현재 입력한 i가 이후에 스도쿠가 안 만들어진다는 뜻이므로 기존의 bt에서 대입했던 값들을 다시 전부 0으로 만든 후 진행. 

 

---

 

n행 m열 칸에 x를 넣으면 충돌하지 않는지 체크하는 함수. 

 

먼저 n행의 줄을 돌면서 체크를 하는데

입력할 칸은 제외하고 x와 같은 숫자가 있으면 안되므로 있다면 false를 리턴한다. 

 

그다음 m열의 줄을 돌면서 입력할 칸은 제외하고 x와 같은 숫자가 있으면  false를 리턴한다. 

 

마지막으로 3*3칸을 체크하는데, 0, 3, 6번째 행과 열이 3*3칸의 시작 행과 열이므로 이를 위해 입력할 n,m행렬에 3을 나눈 몫에 3을 곱해서 만들어준 후

역시나 입력할 칸을 제외하고 x와 같은 숫자가 있다면 false를 리턴한다. 

 

위를 다 돌면 이상이 없다는 뜻이므로 true를 리턴한다. 

 

 

 

---

 

전체코드

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static int[][] board; // 스도쿠 판을 2차원 배열로 구현
    static List<int[]> zeroList; // 숫자가 0인 부분을 따로 (x, y) 좌표로 모아두는 배열 리스트

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

        board = new int[9][9]; // 스도쿠 판을 2차원 배열로 구현
        zeroList = new ArrayList<>(); // 숫자가 0인 부분을 따로 (x, y) 좌표로 모아두는 배열 리스트

        // 입력으로 주어지는 스도쿠판을 돌며 board 배열을 채우고
        // 0인 칸만 따로 그 좌표를 zeroList에 모아둔다
        for (int i = 0; i < 9; i++) {
            String str = br.readLine();
            for (int j = 0; j < 9; j++) {
                int num = str.charAt(j) - '0';
                board[i][j] = num;

                if (num == 0)
                    zeroList.add(new int[]{i, j});
            }
        }

        // 백트래킹으로 모든 zeroList의 값을 1~9중에 대입해보고
        // 스도쿠가 처음으로 완성되면 (= 사전식으로 앞서면) 출력
        bt(0);
    }

    static void bt(int depth) {
        if (zeroList.size() == depth) { // 0인 칸을 전부 채우면
            // 출력 후
            for (int[] row : board) {
                for (int i : row) {
                    System.out.print(i);
                }
                System.out.println();
            }

            System.exit(0); // 이후 더 돌지 않고 프로그램 종료
        }

        int n = zeroList.get(depth)[0]; // n행
        int m = zeroList.get(depth)[1]; // m열

        for (int i = 1; i <= 9; i++) { // 0인 칸을 1~9까지 골라서
            if (isRight(n, m, i)) { // 그 숫자가 가로, 세로, 3*3칸이 이상 없으면
                board[n][m] = i; // 그 칸에 그 숫자 입력 후
                bt(depth + 1); // 다음 0인 칸을 돌기
                // 다시 돌아왔다는 것은 이 숫자가 스도쿠가 안 만들어진다는 뜻이므로 0으로 되돌리기
                board[n][m] = 0;
            }
        }
    }

    // n행 m열의 칸에 숫자 x를 넣으면 스도쿠에 이상이 없는지 체크하는 함수
    static boolean isRight(int n, int m, int x) {
        for (int i = 0; i < 9; i++) { // n행 에서 이상이 없는지 체크
            if (i == m) continue; // 입력할 칸은 넘어가기
            if (board[n][i] == x) return false; // n행 중 하나라도 x와 같은 값이 있으면 스도쿠 실패
        }

        for (int i = 0; i < 9; i++) { // m열에서 이상이 없는지 체크
            if (i == n) continue; // 입력할 칸은 넘어가기
            if (board[i][m] == x) return false; // m열 중 하나라도 x와 같은 값이 있으면 스도쿠 실패
        }

        // 3*3 칸의 시작 행과 열 계산
        int rowStart = (n / 3) * 3;
        int colStart = (m / 3) * 3;

        for (int i = rowStart; i < rowStart + 3; i++) { // 시작 행 ~ +3행
            for (int j = colStart; j < colStart + 3; j++) { // 시작 열 ~ +3열
                if (i == n && j == m) continue; // 입력할 칸은 넘어가기
                if (board[i][j] == x) return false; // 3*3칸 중 x와 같은 값이 있으면 스도쿠 실패
            }
        }

        return true; // 위를 전부 거쳐도 이상 없으면 스도쿠 가능
    }
}