[백준] 2580번 스도쿠(java)

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

2580번: 스도쿠

백트래킹 문제이다.

 

핵심

입력값 0 이 있는 곳에 1~9까지 가능한 숫자를 대입하면서 스도쿠를 완성시켜야 한다.

전형적인 백트래킹 문제이다.

 

 

정답 코드

import java.util.Scanner;

class Main {
    static int[][] map = new int[9][9];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        dfs(0, 0);
    }

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

        if (y == 9) {
            print();
            System.exit(0);
        }

        if (map[y][x] == 0) {
            for (int v = 1; v <= 9; v++) {
                if (validation(y, x, v)) {
                    map[y][x] = v;
                    dfs(y, x + 1);
                }
            }
            map[y][x] = 0;
            return;
        }
        dfs(y, x + 1);
    }

    private static boolean validation(int y, int x, int value) {
        for (int i = 0; i < 9; i++) {
            if (map[y][i] == value) {
                return false;
            }
            if (map[i][x] == value) {
                return false;
            }
        }

        int startY = (y / 3) * 3;
        int startX = (x / 3) * 3;

        for (int i = startY; i < startY + 3; i++) {
            for (int j = startX; j < startX + 3; j++) {
                if (map[i][j] == value) {
                    return false;
                }
            }
        }
        return true;
    }

    private static void print() {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
    }
}

해설

우선 map에 입력값을 넣어준다.

이제 백트래킹을 진행하는데, y와 x의 값을 가지고 진행한다.

x가 9까지 커진다면 y+1을 하고 x는 0으로 변경시킨다. 시작점이 0 이기 때문에 map은 8까지이기 때문이다.

또한 y가 9까지 커진다면 전부 탐색했다는 것을 의미하기 때문에 map을 출력하고 종료시킨다.

 

map [y][x]가 0 이면 1부터 9중에서 대입할 수 있는 숫자를 확인하고 있다면, 넣게 된다.

가능한 수를 대입하고, x를 1 증가시키고 재귀를 한다.

*만약에 0이지만 1부터 9까지 가능한 수가 없다면, map [y][x]를 0으로  만들고 return 한다.

이는 앞의 값이 가능한 다른 값으로 대입하고 다시 돌아오기 위해 사용된다.

 

 

배운 점

처음에는 백트래킹을 사용할 때 y, x좌표를 이용하지 않고 진행하려 하였다.

이렇게 코드를 작성하려 하니 더욱 헷갈리고 복잡해졌다.

문제를 풀 때 영리하게 푸는 방법을 더욱 고민하고 코드를 작성해야겠다.