2239 - 스도쿠 (Java)

 

---

 

문제

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

 

 

풀이

dfs 를 활용하여 푸는 문제이다.

 

배열의 앞쪽에서부터 작은값을 하나씩 대입해보고, 해당 값이 스도쿠 조건에 맞는지 검사하는 식으로 풀이가 가능하다. 

정답이 여러개일경우 사전순으로 출력하라하였기에, 작은 값을 우선적으로 넣어주는 방식으로 풀이했다.

 

우선 값을 입력받고, 이 때 0의 개수를 체크했다. 추후에 0의 개수가 0개가 된다면 정답을 발견한것으로 판단하기 위한 용도이다.

 

이후 2중 for문으로 0 값이 있는 위치를 찾은다음, 해당 위치에 1부터 값을 넣어본다. 선정한 값이 가능한지 여부를 확인하고 (가로, 세로, 3*3 공간) 가능하다면 [1] 배열에 값을 세팅해주고,  [2] 0의 개수를 줄여주고 dfs로 다음 위치를 찾아 반복한다.

 

만약 가능한 값이 없는 경우에는 앞서서 선정한 숫자가 잘못되었다는 뜻이다. 그렇기 때문에 return 으로 이전 단계로 돌아가서 for문을 반복하도록 해야한다. 또한 잘못된 값이기 때문에 배열에 세팅한 값을 원복(0으로) 처리 해주고, 0의 개수도 되돌려 준다.

 

이와 같이 계속 반복하다 보면 0의 개수가 0개가 될 때가 답이므로 출력해주면 된다. 

답을 출력하면 더 이상의 재귀를 할 필요가 없기에 possible 변수를 이용해서 추가적인 연산을 막았다.

 

 

코드

import java.util.*;
import java.io.*;

public class Main {

    public static List<ArrayList<Integer>> sudoku = new ArrayList<>();
    public static int zeroCnt = 0;
    public static boolean possible = false;

    public void dfs(){

        if(possible) return;

        // 결과 출력
        if(zeroCnt == 0){
            for (int i = 0; i < 9; i++) {
                for(int j=0; j<9; j++){
                    System.out.print(sudoku.get(i).get(j));
                }
                System.out.println();
            }
            possible = true;
            return;
        }

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                // 0이 아니면 continue
                if(sudoku.get(i).get(j) != 0) continue;

                // 해당하는 index 에 들어갈 수 있는 수 확인한다.
                for(int k=1; k<=9; k++){

                    // 안되는 값인지 확인한다.
                    if(!check(i, j, k)) continue;

                    // 해당 값(k) 은 되므로 세팅해준다.
                    sudoku.get(i).set(j, k);
                    zeroCnt--;
                    dfs();
                    sudoku.get(i).set(j, 0); // dfs 를 나오면, 0으로 만들어준다.
                    zeroCnt++;
                }
                return;
            }
        }
    }

    public void solution() throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // Initialize
        for (int i = 0; i < 9; i++) {
            String[] line = br.readLine().split("");
            ArrayList<Integer> temp = new ArrayList<>();
            for (String val : line) {
                if(Integer.parseInt(val) == 0) zeroCnt++;
                temp.add(Integer.parseInt(val));
            }
            sudoku.add(temp);
        }

        // dfs 수행
        dfs();
    }

    public boolean check(int row, int col, int val){
        // 수평 줄 검사
        for(int i=0; i<9; i++){
            int target = sudoku.get(row).get(i);
            if(target == val) return false;
        }

        // 수직 줄 검사
        for(int i=0; i<9; i++){
            int target = sudoku.get(i).get(col);
            if(target == val) return false;
        }

        // 범위 검사
        if(row<3) row= 0;
        else if (row<6) row = 3;
        else if (row<9) row = 6;

        if(col<3) col= 0;
        else if (col<6) col = 3;
        else if (col<9) col = 6;

        int xt = row+3;
        int yt = col+3;

        for(int i=row; i < xt; i++){
            for(int j=col; j<yt; j++){
                int target = sudoku.get(i).get(j);
                if(target == val) return false;
            }
        }

        return true;
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

후기

 

꽤 오래걸렸다, 생각해보면 단순 dfs인데.. ㅠ