C# 백준 2580 스도쿠 (백트래킹)

2580번: 스도쿠

IDEA

아주 오래전 군복무 중에 도전했던 문제다. 한창 재귀호출에 대해 (어설프게) 공부하고 있을 때 였는데 백트래킹이라는 것을 연습해보려 몇문제 덤벼들었다가 뼈도 못추린 적이 있었다. 그 때는 대강 이런 알고리즘을 생각했던 것 같다.

 

1. 입력을 받는다. 동시에 빈칸의 수를 센다.

2. 모든 칸을 순차적으로 확인한다.

3. 빈칸이라면 경우의 수를 파악한다.

4. 만약 한 가지 경우의 수만 있다면 그 칸을 채운다.

5. 아니라면 다음 칸을 확인한다.

6. 끝까지 확인했다면 빈칸의 수를 세어본다.

7. 원래 빈칸의 수보다 적다면 빈칸의 수를 새로 저장하고 2로 돌아간다.

8. 끝

 

이 방법을 적용해서 스도쿠 숙제기계를 만들었다. 시도는 훌륭했고 방법도 묘하게 휴리스틱해서 뿌듯했던 기억이 있다. 내가 스도쿠 푸는 방법을 고대로 코드로 만들었던거라 혼자서 "..AI를 창조했다..!" 라고 생각했었다. 하지만 이 코드는 굉장히 쉬운 스도쿠만 풀어줄 수 있으며 어려운 문제가 주어지거나 답이 여러개인 문제가 주어진다면 빈칸을 남발하고 인간에게 짬때리는 정신이 나간 코드였다. 지금의 나는 그 때보다 더 많은 것을 배웠으며 무엇보다 깊이우선탐색의 원리와 방법을 안다. 그것을 써먹기로 했다. 다만 요즘 한참 풀고있는 어떤 문제에서 재귀를 탈출할 때 매개변수의 원래 값을 불러오지 못하는 부분이 골머리를 썩게 만들고 있어서 이번에는 매개변수를 넘겨주는 재귀호출이 아닌 Stack을 이용해 매개변수를 관리하는 방법을 적용해봤다. 이런 원시적인 코딩도 해봐야 원리를 정확히 알 것 아닌가.

 

알고리즘은 다음과 같다.

 

1. 입력을 받는다. 동시에 빈칸들은 '확인할' Stack에 저장한다. (때문에 탐색을 시작하면 역순으로 시작하게 된다.)

2. '확인할' Stack에 저장된 칸을 불러와 i를 대입해본다. i의 초기값은 1이고 10이 되면 7을 실행한다.

3. 가로, 세로, 박스(3*3 크기의 작은 구역)에 중복되는 숫자가 없다면 현재 값을 '확인한' Stack에 넘겨준 다음 재귀호출한다.

4. 중복되는 숫자가 있다면 i++하고 2로 돌아간다.

5. 중복되는 숫자가 있다면 현재 구역을 0으로 재설정하고 return한다.

6. '확인할' Stack에 데이터가 없다면 탐색이 성공적으로 끝난 것이다. return한다.

7. 탐색이 실패했다. return하기 전에 '확인한' Stack에서 값 하나를 '확인할' Stack으로 넘겨주고 2로 돌아간다.

 

코드는 성공적이었다.

using System;
using System.Collections.Generic;
public class Location   // 좌표 형식을 만드는 클래스
{
    private int x, y;
    public int X
    {
        get { return this.x; }
        set { this.x = value; }
    }
    public int Y
    {
        get { return this.y; }
        set { this.y = value; }
    }
    public Location(int a, int b)
    {
        X = a; Y = b;
    }
}
class Program
{
    static int[,] sudoku = new int[9, 9];
    static Stack<Location> checklist = new Stack<Location>();
    // '확인할' Stack

    static Stack<Location> checkedlist = new Stack<Location>();
    // '확인한' Stack
    static void Main()
    {
        for (int i = 0; i < 9; i++)
        {
            var row = Console.ReadLine().Split();
            for (int j = 0; j < 9; j++)
            {
                sudoku[i, j] = int.Parse(row[j]);
                if (sudoku[i, j] == 0) checklist.Push(new Location(i, j));
            }
        }

        Tracking();

        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
                Console.Write(sudoku[i, j] + " ");
            if (i != 8) Console.Write("\n");
        }
    }

    static void Tracking()
    {
        if (checklist.Count == 0) return;
        int a = checklist.Peek().X; int b = checklist.Peek().Y;
        for (int i = 1; i < 10; i++)
        {
            sudoku[a, b] = i;
            if (Check(checklist.Peek()))
            {
                checkedlist.Push(checklist.Pop());
                // 가능한 숫자라면 Stack을 하나 옮긴다.
                Tracking(); // 재귀호출
            }
            else continue;
                // 불가능한 칸이면 다음 숫자를 확인한다.
            if (checklist.Count == 0) return;
            // 여기를 왔다는 건 재귀를 탈출했다는 뜻이고
            // '확인한' Stack이 비었다는 것은 스도쿠를 완성했다는 뜻이다.
            // 재귀 탈출
        }
        // 여기로 넘어왔다는 것은 모든 숫자가 불가능했고 이번 탐색은 실패라는 뜻이다.
        // 상위 호출로 돌아가서 다음 숫자를 받고 다시와야한다.
        sudoku[a, b] = 0;   // 가기전에 지금 위치를 원래대로 돌려놓고
        checklist.Push(checkedlist.Pop());
        // '확인한' Stack을 '확인할' Stack으로 다시 돌려준다.
    }

    static bool Check(Location s)   // 가능한 칸인지 확인하는 메소드
    {
        int a = s.X; int b = s.Y;
        for (int i = 0; i < 9; i++)
        {
            if (i != a && sudoku[i, b] == sudoku[a, b]) return false;
            if (i != b && sudoku[a, i] == sudoku[a, b]) return false;
            // 가로 세로에 같은 숫자가 있는지 하나하나 확인한다.
            // 벌써부터 비효율적인걸
        }
        a /= 3; b /= 3;
        a *= 3; b *= 3;
        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                if (s.X == a + i && s.Y == b + j) continue;
                if (sudoku[s.X, s.Y] == sudoku[a + i, b + j]) return false;
                // 같은 박스 안에 같은 숫자가 있는지 확인한다.
            }
        }
        return true;
    }
}​

이 코드는 매우 잘 작동하며 (사람기준) 매우 빠르게 모든 스도쿠를 풀어주는 것 처럼 보인다. 하지만 빈칸에 숫자를 대입해 가능한지 살펴보는 부분이 문제였다. 위 코드의 방법으로는 매번 가로 8칸, 세로 8칸, 박스 8칸을 전부 확인해야한다. 모든 칸이 비어있다면 모든 칸에 대해 전부 확인해야하고 한번에 가능한 숫자를 찾는다 쳐도 8 * 3 * 81 = 1944번 확인하는 놀라운 비효율적 코드다. 잘못된 탐색으로 되돌아가는 경우와 1~9까지를 모두 대입해보는 것들을 더해서 계산해준다면 확인하는 횟수는 아마 수만번으로 늘어날거다. 탐색 횟수를 줄여야한다.

 

다행히 탐색 횟수를 줄여줄 방법은 금방 떠올랐다. 그냥 어떤 칸의 가로, 세로, 박스에 이 숫자가 있는지 기록하는 배열만 만들어주면 된다. 그러면 어떤 숫자에 대한 가능여부 탐색 횟수는 칸당 24회에서 3회로 줄어든다.

 

CODE

using System;
using System.Collections.Generic;
public class Location
{
    private int x, y;
    public int X
    {
        get { return this.x; }
        set { this.x = value; }
    }
    public int Y
    {
        get { return this.y; }
        set { this.y = value; }
    }
    public Location(int a, int b)
    {
        X = a; Y = b;
    }
}
class Program
{
    static int[,] sudoku = new int[9, 9];
    static bool[,] row = new bool[9, 9];    // 가로 정보를 기록할 배열
    static bool[,] col = new bool[9, 9];    // 세로 정보를 기록할 배열
    static bool[,] box = new bool[9, 9];    // 박스 정보를 기록할 배열
    static Stack<Location> checklist = new Stack<Location>();
    static Stack<Location> checkedlist = new Stack<Location>();
    static void Main()
    {
        for(int i = 0; i < 9; i++)
        {
            var r = Console.ReadLine().Split();
            for(int j = 0; j < 9; j++)
            {
                sudoku[i, j] = int.Parse(r[j]);
                if (sudoku[i, j] == 0) checklist.Push(new Location(i, j));
                else Marker(i, j);
            }
        }

        Tracking();

        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
                Console.Write(sudoku[i, j] + " ");
            if(i != 8) Console.Write("\n");
        }
    }
    static void Marker(int a, int b)
    {
        row[a, sudoku[a, b] - 1] = !row[a, sudoku[a, b] - 1];
        col[b, sudoku[a, b] - 1] = !col[b, sudoku[a, b] - 1];
        box[(a / 3) * 3 + b / 3, sudoku[a, b] - 1]
            = !box[(a / 3) * 3 + b / 3, sudoku[a, b] - 1];
        // 이 메소드는 어떤 칸의 어떤 숫자에 대한 가능 여부를
        // 반대로 바꿔주는 메소드다.
    }
    static bool Check(Location s, int k)
    {
        int a = s.X; int b = s.Y;
        if (row[a, k - 1] || col[b, k - 1] || box[(a / 3) * 3 + b / 3, k - 1]) return false;
        // 굉장히 짧아진 코드를 확인할 수 있다.
        else return true;
    }
    static void Tracking()
    {
        if (checklist.Count == 0) return;
        int a = checklist.Peek().X; int b = checklist.Peek().Y;
        for (int i = 1; i < 10; i++)
        {
            if (Check(checklist.Peek(), i))
            {
                checkedlist.Push(checklist.Pop());  // Stack 넘겨주기
                sudoku[a, b] = i;                   // 칸에 숫자 대입하기
                Marker(a, b);                       // 대입한 숫자 가능여부 반대로 바꾸기
                Tracking();                         // 다음 호출
            }
            else continue;
            Marker(a, b);                           // 숫자 가능여부 반대로 바꾸기
            if (checklist.Count == 0) return;       // 탐색 성공했으면 탈출
        }
        checklist.Push(checkedlist.Pop());          // Stack 되돌리기
    }
}

이제 이런걸 열심히 풀고 문제 출처를 봤을 때

이런걸 보게 되면 정말 현타가 강하게 온다.

나.. 성공할 수 있을까..?