[백준] 2239: 스도쿠 (dfs) - JAVA

class 5

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

 

 

 

# 문제

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

 

 

 

# 예제

입력 :  9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

 

출력 :  9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

 

# 필요개념

출력조건은 어렵게 생각할 것 없이 값을 오름차순으로 넣어보면 해결된다. 스도쿠를 할 때 들어갈 수 있는 숫자의 조건은 다음과 같다.

• 같은 열에 중복된 숫자가 있으면 안 됨
• 같은 행에 중복된 숫자가 있으면 안 됨
• 같은 사각형 (같은 색을 가진 3X3 사각형) 에 중복된 숫자가 있으면 안 됨

따라서 나는 5개의 함수를 만들었다.

• 같은 열에 중복된 숫자 존재 여부 확인 (len())
• 같은 행에 중복된 숫자 존재 여부 확인 (wid())
• 같은 사각형에 중복된 숫자 여부 확인 (square())
  • 사각형 범위 찾는 함수 (range())
• 스도쿠를 플레이 할 함수 (재귀 사용) - play()

 

 

이제와서 생각해보니 위 함수들을 이용해서 조건을 판별하는 함수를 하나의 함수로 만들어도 좋았을 거 같다는 생각이 든다!

 

play 함수를 구현할 때 원래는 y와 x 인덱스값을 따로 넘기려고 했는데 새로운 행으로 넘어갈 때 숫자 넣기가 애매해져서 고민이 되었다. 그래서 찾아보니 몇번쨰 칸인지를 인수로 받고, 9로 나눈 몫을 y, 나머지를 x로 이용하는 사람들이 많았다. 이렇게 하면 종료조건을 쓰기도 편하고 좋은 거 같아 나도 이용하기로 했다.

 

그리고 끝났는지 여부는 종료시 boolean타입의 변수를 이용해 판별하기로 했다.

 

# Code

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

public class Main {
    static int[][] sudoku;
    static boolean finish = false;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sudoku = new int[9][9];

        for (int i = 0 ; i < 9 ; i++) {
            String str = br.readLine();
            for (int j = 0 ; j < 9 ; j++) {
                sudoku[i][j] = Integer.parseInt(String.valueOf(str.charAt(j)));
            }
        }


        play(0);

        StringBuilder sb = new StringBuilder();
        for (int i = 0 ; i < 9 ; i++) {
            for (int j = 0 ; j < 9 ; j++) {
                sb.append(sudoku[i][j]);
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }

    private static void play(int depth) {
        boolean start = true;
        // y를 depth의 몫, x를 나머지로 접근함
        if (depth == 81) {
            finish = true;
            return;
        }

        int y = depth / 9;
        int x = depth % 9;

        if (sudoku[y][x] != 0) play(depth + 1);
        else {
            for (int v = 1 ; v <= 9 ; v++) {
                if (len(x, v) && wid(y, v) && square(y, x, v)) {
                    sudoku[y][x] = v;
                    play(depth + 1);
                    if (finish) return;
                    sudoku[y][x] = 0;
                }

            }
        }
    }

    private static boolean square(int ii, int jj, int value) {
        int y = range(ii);
        int x = range(jj);
        for (int i = y ; i <= y + 2 ; i++) {
            for (int j = x ; j <= x + 2 ; j++) {
                if (sudoku[i][j] == value) return false;
            }
        }
        return true;
    }

    private static boolean wid(int i, int value) {
        // 가로 탐색
        for (int j = 0 ; j < 9 ; j++) {
            if (sudoku[i][j] == value) return false;
        }
        return true;
    }

    private static boolean len(int j, int value) {
        // 세로 탐색
        for (int i = 0 ; i < 9 ; i++) {
            if (sudoku[i][j] == value) return false;
        }
        return true;
    }

    private static int range(int y) {
        if (y >= 0 && y <= 2) return 0;
        else if (y >= 3 && y <= 5) return 3;
        else return 6;
    }
}

 

 

 

# 결과