[BOJ - JAVA] 2580 - 스도쿠 (DFS)

# 주소

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

2580번: 스도쿠

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
public class Main {
    static int arr[][];
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        arr = new int[9][9];
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                arr[i][j] = scan.nextInt();
            }
        }
        dfs(0,0);
    }
    public static void dfs(int x, int y){
        if(y == 9){
            dfs(x+1,0);
            return;
        }
        if(x == 9){
            for(int i = 0; i < 9; i++){
                for(int j = 0; j < 9; j++){
                    System.out.print(arr[i][j] + " ");
                }
                System.out.println();
            }
            System.exit(0);
        }
        if(arr[x][y] == 0){
            for(int i = 1; i <= 9; i++){
                if(possibility(x,y,i)){
                    arr[x][y] = i;
                    dfs(x,y+1);
                }
            }
            arr[x][y] = 0;
            return;
        }
        dfs(x,y+1);
    }
    public static boolean possibility(int x, int y, int t){
        for(int i = 0; i < 9; i++){
            if(arr[x][i] == t){
                return false;
            }
        }
        for(int i = 0; i < 9; i++){
            if(arr[i][y] == t){
                return false;
            }
        }
        int nx = (x / 3) * 3;
        int ny = (y / 3) * 3;
        for(int i = nx; i < nx + 3; i++){
            for(int j = ny; j < ny + 3; j++){
                if(arr[i][j] == t){
                    return false;
                }
            }
        }
        return true;
    }
}

https://codingrapper.tistory.com/137

[BOJ - JAVA] 9663 - N-Queen (백트래킹)

예전에 풀었던 N-Queen의 문제와 푸는 방식이 비슷하지요???

스도쿠의 기본 개념 자체가 어렵지 않기 때문에 조금만 생각을 하시면 그리 어렵지 않습니다.

9 x 9 배열이기 때문에 arr문을 이중 for문으로 입력받습니다.

dfs에 0,0 을 넣고 실행하겠습니다. (0,0이 시작점)

 

dfs구문으로 들어갑니다.

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

이부분은 만약 y == 9라면 다음 dfs(x+1,0)으로 갑니다.

이 y값은 열을 의미합니다.

그리고 if(x == 9) 이 부분은 나중에 설명하겠습니다.

쭉 내려와서 if(arr[x][y] == 0) 인 지점을 살펴봅시다.

arr[x][y] == 0인 곳을 우리가 채우는 것이 목표입니다.

그에 따라서 만약 x,y위치에 임의의 i점을 넣어보고 그 점이 들어갈 수 있는 점인지 확인하는 함수인 possibility함수를 실행합니다. 

계속 내려갑시다. possibility는 어떻게 생겼는지 보지요.

public static boolean possibility(int x, int y, int t){
        for(int i = 0; i < 9; i++){
            if(arr[x][i] == t){
                return false;
            }
        }
        for(int i = 0; i < 9; i++){
            if(arr[i][y] == t){
                return false;
            }
        }
        int nx = (x / 3) * 3;
        int ny = (y / 3) * 3;
        for(int i = nx; i < nx + 3; i++){
            for(int j = ny; j < ny + 3; j++){
                if(arr[i][j] == t){
                    return false;
                }
            }
        }
        return true;

 

제일 먼저 x,y위치의 t점에 대해 만약 arr[x][i]이 t가 되는지 확인합시다.

만약 arr[x][i] == t인 점이 존재한다면 (한 행에 똑같은 점이 이미 있다면) 이 possibility함수는 false를 return해야합니다.

그리고 arr[i][y]가 t인 점이 존재한다면 (한 열에 똑같은 점이 이미 있다면) 이 possibility하무도 false입니다.

만약 여기까지 다 true라면 해당 점의 위치에서 행,열에 중복된 점이 없다는 것이겠지요.

그러면 마지막으로 확인할 것은, 3x3박스 내부에 똑같은 점이 있는지의 여부입니다.

nx와 ny를 새로 만들겠습니다.

왜냐하면 nx의 위치가 2행 2열이라면 9개의 3x3직사각형 중 첫번쨰로 들어갈 것이고, 5행6열이라면 5번쨰 박스에 들어갈 것입니다.

이중 for문에 대해서 만약 arr[i][j]가 t와 같은 점이 있다면 return false를 보냅니다.

만약 모든 i,j가 무사 통과했다면 해당 3x3박스안에 같은 점이 없으므로 true를 return하고 해당 possibility는 i점을 x,y위치에 사용할 수 있게됩니다.

따라서 arr[x][y] 에는 i점을 넣고, dfs로서는 다음 열로 이동합니다.

그런데 스도쿠 문제를 풀다보면 중복되지 않는 수를 넣다가 나중에 어쩔수없이 중복되는 수가 존재할 수가 있습니다.

이럴 경우엔 possibility가 모두 false이므로 arr[x][y] = 0을 넣고 return을 시킵니다.

그러면 다시 백트래킹 되어서 순차적으로 숫자를 끼워맞추는... 그런 함수가 되는데요.

어려운건 없지만 어렸을 때 스도쿠를 참 좋아해서 동아리도 스도쿠반을 2년 했었는데 그 기억도 나서 좋았네요.

다음엔 CS랑 플젝 코딩도 슬슬 해보려합니다.

감사합니다.