백준 2580번 : 스도쿠 [C#]

1. 보드판을 돌며 0을 만났을 때 1부터 9까지 넣어보고 가능한 숫자가 있으면 이어가고, 없으면 return 같다.

> 0인 좌표를 순회하면서 1~9를 다 넣어 본 다음에 방법이 없으면 돌아와서 상태 복원을 해야한다.

 

2. 어떻게 가능한지 확인할까?

> 행, 열, 3*3 에 같은 숫자가 없어야 한다.

> 모두 비교하면 너무 느리지 않을까? > 0칸이 N개 있으면 최악의 경우 N*9*9*9*9 이고, 항상 9까지 검사하진 않으니까 조금 낫겠지다.

 

3. 재귀의 편의를 위해 0의 좌표를 튜틀형태로 리스트에 저장해두고 이 리스트에서 다음 0의 좌표를 꺼내서 비교해가며 보드판을 채우고, index가 리스트의 크기일 때 반환하도록 했다.

 

* 이 문제에서의 포인트는 코드에서 row, col, x, y, i, j 를 혼용하여 헷갈리면서 시간이 오래걸린점이다. 앞으로는 가능하면 익숙한 row, col으로 통일해야겠다.

 

using System.Numerics;
using System.Text;

class Program
{

    static int N;

    static int[,] board = new int[9, 9];

    static List<(int r, int c)> zeros = new List<(int r, int c)>(); // 0이 들어있는 좌표를 튜플로 저장


    static void WriteBoard() // 출력
    {
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                Console.Write(board[i, j] + " ");
            }
            Console.WriteLine();
        }
    }

    static bool Sudoku(int index) // 메인 순회, index는 zeros의 index이다. = 몇 번째 0 좌표인지
    {
        if (index == zeros.Count)
        {
            WriteBoard();
            return true;
        }

        int row = zeros[index].r;
        int col = zeros[index].c;

        for (int n = 1; n <= 9; n++)
        {
            if (IsPossible(n, row, col))
            {
                board[row, col] = n;

                if (Sudoku(index+1))
                {
                    return true;
                }
                board[row, col] = 0;
            }
        }
        return false;
    }

    static bool IsPossible(int n, int row, int col)
    {
        // 행 검사
        for (int i = 0; i < 9; i++)
        {
            if (board[i, col] == n) return false;
        }

        // 열 검사
        for (int i = 0; i < 9; i++)
        {
            if (board[row, i] == n) return false;
        }

        // 3*3 검사

        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        
        for (int i = startRow; i < startRow + 3; i++)
        {
            for (int j = startCol; j < startCol + 3; j++)
            {
                if (board[i, j] == n) return false;
            }
        }

        return true;
    }

    static void Main()
    {
        for (int i = 0; i < 9; i++)
        {
            string[] line = Console.ReadLine().Split();

            for (int j = 0; j < 9; j++)
            {
                board[i, j] = int.Parse(line[j]);
                if (board[i, j] == 0) zeros.Add((i, j));
            }
        }
        
        Sudoku(0);
    }

}