[백준 2580] 스도쿠

[jusung-c]

2580번: 스도쿠 (acmicpc.net)

---

아이디어

재귀로 완전탐색하는 부분과 위의 2조건을 판단하는 부분을 따로 만들어 생각한다.

탐색 부분

행과 열을 전체적으로 돌면서 탐색하니까 재귀함수 rec_func의 파라미터는 행과 열로 지정해주었다.

private static void rec_func(int row, int col)

먼저 row 행을 기준으로 col 열을 1열부터 9열까지 돌면서 숫자가 채워지지 않은 부분 (0인 부분)을 찾아서
for문으로 1~9까지 수 중에서 스도쿠 조건에 맞는 수를 찾아서 map을 업데이트 해준다.

단, 여기서 만약 1~9까지 모든 수가 불가능할 경우 이 케이스는 버리고 다시 탐색하기 위해 초기화와 return을 해준다.

// 숫자가 0으로 비어있으면 탐색 시작
if (map[row][col] == 0) {
    for (int i = 1; i <= 9; i++) {

        // 모든 조건 체크
        if (check(row, col, i)) {
            map[row][col] = i;

            // 다음 열 탐색
            rec_func(row, col+1);
        }
    }

    // 맞는 케이스를 못찾았을 경우를 위한 초기화와 return
    map[row][col] = 0;
    return;
}

여기서 만약 return을 안해주고 테스트 케이스를 돌려보면 다음과 같이 나온다.

// 입력
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

// 출력
1 2 3 4 5 6 7 8 9 
4 5 6 1 2 3 0 0 0 
7 8 9 0 0 0 1 2 3 
2 1 4 3 6 5 8 7 0 
3 6 5 2 1 4 9 0 0 
8 7 0 9 0 0 2 1 4 
5 3 1 6 4 2 0 9 7 
6 4 2 5 3 1 0 0 8 
9 0 7 8 0 0 3 4 1

1~9까지 들어갈 수 있는 수가 없으면 map을 초기화해주고 다시 그 전 깊이의 상위 rec_func()의 다음 후보부터 다시 탐색해야 하는데 초기화만 해주고 return을 안해줘서 틀린 경우를 끝까지 탐색 후 출력한 것이다. 0이 처음부터 채워지다가 어느순간부터 안채워진 map을 볼 수 있다.

찾고 있던 행의 열을 다 탐색했으면 다음 행을 넘어가고 마지막 행까지 다 탐색하면 출력해준다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력해야 하니까 한 케이스 출력 후에 바로 프로그램을 종료시켜줘야 한다.

// 현재 행의 열이 다 채워지면 다음 행부터 다시 1열 ~ 9열 탐색
if (col == 10) {
    rec_func(row + 1, 1);
    return;
}

// 여러 경우의 수가 있겠지만 1개 찾으면 그자리에서 출력 후 바로 종료
if (row == 10) {
    print(map);
    bw.close();
    System.exit(0);
}

단, 여기서도 마찬가지로 return이 중요하다. 이 return이 없이 제출을 해보면 런타임 에러 (ArrayIndexOutOfBounds)로 틀리게 된다.

여기서도 아까의 return처럼 만약 더 이상 채울 수 없고 지금의 탐색이 틀린 케이스라는 것을 깨달았을 때 그 행의 열 뿐만 아니라 그 전 행, 그 전전 행까지 다시 백트래킹을 해줘야 하기 때문에 틀릴 경우를 대비해 상위 rec_func()로 가게 해주는 return을 적어주는 것이다.

---

시간 복잡도

후하게 9x9 크기의 map을 1~9 다 넣어본다고 생각하면 9 x 9 x 9이라서 1초 안에 해결 가능하다

---

음.. 이번에도 글로 잘 설명하는 걸 실패한 것 같다..

처음에 rec_func()의 파라미터를 뭘로 해야 할 지 생각하지 못했다. 당연히 map의 전체를 첫행부터 마지막행까지 탐색하려면 row와 col을 인자로 넘겨줬어야 했는데 이상한 삽질만 40분 하다가 힌트만 보려고 살짝 풀이 보고 알아챘다.

그러고 다시 혼자 해보는데 이번엔 행, 열, 3x3 체크하는 거에서 행, 열까지는 혼자 생각했는데 3x3 조건을 체크하는 게 어려웠다. 결국 풀이를 봤다...

---

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int[][] map;

    public static void main(String[] args) throws IOException {
        init();

        // 1행 1열부터 탐색 시작
        rec_func(1, 1);

    }

    private static void rec_func(int row, int col) throws IOException {
        // 현재 행의 열이 다 채워지면 다음 행부터 다시 1열 ~ 9열 탐색
        if (col == 10) {
            rec_func(row + 1, 1);
            return;
        }

        // 여러 경우의 수가 있겠지만 1개 찾으면 그자리에서 출력 후 바로 종료
        if (row == 10) {
            print(map);
            bw.close();
            System.exit(0);
        }

        // 숫자가 0으로 비어있으면 탐색 시작
        if (map[row][col] == 0) {
            for (int i = 1; i <= 9; i++) {

                // 모든 조건 체크
                if (check(row, col, i)) {
                    map[row][col] = i;

                    // 다음 열 탐색
                    rec_func(row, col+1);
                }
            }

            // 맞는 케이스를 못찾았을 경우를 위한 초기화와 return
            map[row][col] = 0;
            return;
        }

        // 이미 숫자가 적혀있으면 다음 열로 ㄱㄱ
        rec_func(row, col + 1);
    }

    static boolean check(int row, int col, int value) {

        // 행 check
        for (int i = 1; i <= 9; i++) {
            if (map[row][i] == value) {
                return false;
            }
        }

        // 열 check
        for (int i = 1; i <= 9; i++) {
            if (map[i][col] == value) {
                return false;
            }
        }

        // 3x3 check
        int x = ((row - 1) / 3) * 3;
        int y = ((col - 1) / 3) * 3;

        for (int i = x+1; i <= x + 3; i++) {
            for (int j = y+1; j <= y + 3; j++) {
                if (map[i][j] == value) {
                    return false;
                }
            }
        }

        return true;
    }

    // map 출력
    static void print(int[][] map) throws IOException {
        for (int i = 1; i <= 9; i++) {
            for (int j = 1; j <= 9; j++) {
                bw.write(map[i][j] + " ");
            }
            bw.write("\n");
        }
    }

    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        map = new int[10][10];

        for (int i = 1; i <= 9; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 1; j <= 9; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }
}

---

[ghdcksgml1]

열심히 푼 당신에게 선물을 드리겠습니다!

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

입출력만 조금 바꿔주면 바로 맞출 수 있습니다. ㅋㅋㅋㅋ

[jusung-c]

ㅋㅋㅋㅋㅋㅋㅋ선물맞죠?

[jusung-c]

선물맞네여 진짜ㅋㅋㅋ

[BanApp]

백준 풀때 저런 그림 나오면 자연스럽게 뒤로가기 누르고 싶어집니다..

[jusung-c]

인정합니다.. 미루고 미루다가 필수문제라서 어쩔 수 없이..