백준 2580번 스도쿠 :: 마이구미

이 글은 백준 알고리즘 문제 2580번 "스도쿠" 를 풀이한다.

일반적으로 알고 있는 스도쿠 문제를 해결하는 과정을 그대로 구현하는 것이다.

본인은 스도쿠 문제를 풀어본 적이 없다.

그렇기에 스도쿠 관련 알고리즘을 사용한 것이 아닌, 단순히 규칙만을 가지고 접근했다.

문제 풀이의 핵심은 백트래킹을 활용한다.

참고 링크 - http://www.geeksforgeeks.org/backtracking-set-7-suduku/

DFS, BFS - http://mygumi.tistory.com/102

백준 문제 - https://www.acmicpc.net/problem/2239

스도쿠 문제를 풀기 위한 일반적인 규칙은 다음과 같다.

스도쿠에 대해 굳이 자세히 다루지는 않겠다.

일반적으로 빈칸에 해당하는 가로줄 또는 세로줄 또는 같은 박스에는 같은 수가 있으면 안된다.

1. 가로줄

2. 세로줄

3. 같은 박스

세가지 경우를 모두 체크해보고 넣을 수 있는 수가 있다면, 그 수를 넣으면 된다.

일반적으로 다음과 같은 형태로 구현된다.

public static boolean isSafe(int n, int r, int c) {
    if (checkRow(r, n) && checkCol(c, n, 0) && checkBox(r, c, n)) {
        return true;
    }
    return false;
}

하지만 많은 경우가 있기 때문에, 한번에 넣을 수 있을 가능성이 희박하다.

그렇기에 넣을 수 있는 수를 넣어보면서, 아니면 다시 다른 수를 넣어보기 위해 백트래킹을 활용한다.

빈칸이 있다면 1부터 9까지 넣을 수 있는 수를 넣고 다음 빈칸을 찾아 이 과정을 반복한다.

빈칸에 넣을 수 있는 수가 없다면, 백트래킹을 통해 이전 수를 넣을 수 있는 다음 수로 넣어본다.

이 과정이 반복되는 것이다.

public static boolean fill() {
    int r = 0;
    int c = 0;

    if (findEmpty()) {
        return true;
    }

    r = currentRow;
    c = currentCol;

    for (int n = 1; n <= 9; n++) {
        if (isSafe(n, r, c)) {
            map[r][c] = n;
            if (fill()) {
                return true;
            }
            // failure
            map[r][c] = 0;
        }
    }
    // backtracking
    return false;
}

스도쿠 관련 알고리즘은 각 알고리즘마다 이름이 있을정도다.

이 글의 풀이에서는 그 알고리즘을 다룬 것이 아닌 일반적인 접근이라고 보면 된다.

Github 전체 코드 - https://github.com/hotehrud/acmicpc/blob/master/algorithm/graph/2239.java