BOJ 2580 - 스도쿠

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

2580번: 스도쿠

 

---

 

 

스도쿠 판을 표현한 2차원 배열 ARR[][] 에서 0이 위치한 (x, y) 좌표에 적당한 값을 넣어 스도쿠를 완성시키는 문제이다.

 

(x, y) 좌표에 올바른 값 (value) 이 오기 위한 조건은 다음과 같다.

• ARR[x][0~8] 값과 value 가 같으면 안된다.
• ARR[0~8][y] 값과 value가 같으면 안된다.
• (x, y) 좌표 기준 3*3 범위 안에서 value가 같으면 안된다.
  -> 3*3 범위는 다음과 같다. ARR[(x/3)*3 ~ (x/3)*3 + 3][(y/3)*3 ~ (y/3)*3 + 3]

이전 문제와 같이 다음 조건들을 isPossible이란 함수로 표현하고 boolean 타입을 반환하였다.

 

주의해야 할 점은 스도쿠판을 채우는 경우의 수는 여러가지가 있을 수 있다.

문제에 여럿인 경우 하나만을 출력해야 한다고 명시되어 있으니, 프로그램을 강제 종료시켜 계속해서 순회도는 것을 막는다.

 

코드는 다음과 같다.

 

 

 

 

 

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

public class Main {
    static int[][] ARR = new int[9][9];
    static StringBuilder SB = new StringBuilder();

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

        for (int i = 0; i < 9; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 9; j++) {
                ARR[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs(0, 0);
    }

    public static void dfs(int x, int y) {
        if (y == 9) {
            dfs(x + 1, 0);

            return;
        }

        // x가 9가 될 때는 순회가 1번 다 끝났을 때이다.
        if (x == 9) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    SB.append(ARR[i][j] + " ");
                }
                SB.append("\n");
            }

            System.out.println(SB);
            System.exit(0);
        }

        // 수도쿠 판 중 비어있는 값일 있을 때
        if (ARR[x][y] == 0) {
            for (int i = 1; i < 10; i++) {
                // 비어있는 값에 1~9 중 들어갈 수 있는 숫자를 찾는다.
                if (isPossible(x, y, i)) {
                    ARR[x][y] = i;
                    dfs(x, y + 1);
                }
            }

            // 1~9 중 (x,y) 좌표에 가능한 값이 없으면 return 시켜서 이전 값을 바꾸도록 유도한다.
            ARR[x][y] = 0;

            return;
        }

        dfs(x, y + 1);
    }

    // value 가 (x, y) 좌표에 올 수 있는 값인지 확인한다.
    public static boolean isPossible(int x, int y, int value) {
        for (int i = 0; i < 9; i++) {
            // 가로에 같은 숫자가 있는지 확인한다.
            if (ARR[x][i] == value) {
                return false;
            }

            // 세로에 같은 숫자가 있는지 확인한다.
            if (ARR[i][y] == value) {
                return false;
            }
        }

        // 3*3 좌표에 같은 숫자가 있는지 확인한다.
        int startX = (x / 3) * 3;
        int startY = (y / 3) * 3;
        for (int i = startX; i < startX + 3; i++) {
            for (int j = startY; j < startY + 3; j++) {
                if (ARR[i][j] == value) {
                    return false;
                }
            }
        }

        return true;
    }


}