자바(Java) 백준 2580 스도쿠 풀이

문제

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

2580번: 스도쿠

풀이

9 * 9의 네모안에서 값이 0인 지점들을 스도쿠 규칙에 따라 올바른 숫자로 채우는 문제입니다. 스도쿠 규칙은 다음 3가지를 충족하면 됩니다.

• 가로 9칸의 숫자가 모두 달라야합니다.
• 세로 9칸의 숫자가 모두 달라야합니다.
• 3 * 3의 작은 네모안에 있는 9칸의 숫자가 모두 달라야합니다.

다음의 순서로 풀이합니다.

1. 0 값을 갖고 있는 지점들을 List<Point>에 저장합니다.
2. dfs를 통해 list값 순서대로 해당 지점에 1 ~ 9 까지의 숫자를 조건에 맞는지 확인 후에 넣습니다.
3. isPos() 메소드를 사용하여 3가지 조건이 충족하는지 체크합니다.
4. 리스트 안의 모든 0 값을 다른 숫자로 변경하였다면 스도쿠를 출력합니다.
5. 이 때 충족하는 스도쿠를 한 번만 출력하기 위해 flag 변수를 사용하여 체크합니다.

코드

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

public class Main {

    private static int[][] board = new int[9][9];
    private static List<Point> pointList = new ArrayList<>();
    private static boolean flag = false;

    // 0인 점들을 저장하기 위한 클래스
    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

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

        for (int i = 0; i < 9; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 9; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                if (board[i][j] == 0) {
                    // 해당 점이 0일 경우 pointList에 저장
                    pointList.add(new Point(i, j));
                }
            }
        }

        dfs(0);
    }

    public static void dfs(int idx) {
        if (idx == pointList.size()) {
            // 한 가지 경우의 수만 출력하기 위해 flag 값으로 이미 출력을 했는지 체크합니다.
            if (flag) {
                return;
            }
            flag = true;
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    System.out.print(board[i][j] + " ");
                }
                System.out.println();
            }
            return;
        }

        Point p = pointList.get(idx);
        // 1 ~ 9 까지의 수 중에서 가능한 숫자를 찾습니다.
        for (int i = 1; i < 10; i++) {
            if (isPos(p.x, p.y, i)) {
                board[p.x][p.y] = i;
                dfs(idx + 1);
                board[p.x][p.y] = 0;
            }
        }
    }

    public static boolean isPos(int x, int y, int num) {
        for (int i = 0; i < 9; i++) {
            // 해당 점의 세로에 num과 같은 값이 있는지 확인합니다.
            if (board[i][y] == num) {
                return false;
            }
            // 해당 점의 가로에 num과 같은 값이 있는지 확인합니다.
            if (board[x][i] == num) {
                return false;
            }
        }

        int startX = (x / 3) * 3;
        int startY = (y / 3) * 3;
        // 해당 점의 3 * 3 크기의 작은 네모안에 num과 같은 값이 있는지 확인합니다.
        for (int i = startX; i < startX + 3; i++) {
            for (int j = startY; j < startY + 3; j++) {
                if (board[i][j] == num) {
                    return false;
                }
            }
        }

        return true;
    }
}