[BOJ][C#] 2580 스도쿠

📕 문제

📌 링크

📗 접근 방식

빈 칸 찾기:

• 입력된 스도쿠 보드에서 빈 칸(0)의 위치를 저장한다.

백트래킹을 통한 스도쿠 완성:

• 백트래킹을 활용하여 스도쿠를 완성한다.
• 빈 칸 중 첫 번째 빈 칸을 선택하고, 1부터 9까지의 숫자 중 가능한 숫자를 찾는다.
• 해당 숫자가 현재 위치의 행, 열, 3x3 박스에 중복되지 않으면 그 값을 할당하고 다음 빈 칸으로 이동한다.
• 만약 해당 숫자가 중복된다면 다음 숫자를 시도한다.
• 모든 숫자를 시도해도 중복이 발견되지 않으면 다시 이전 빈 칸으로 돌아가서 다른 숫자를 시도한다.

결과 출력:

• 스도쿠를 완성한 후, 완성된 스도쿠 보드를 출력합니다.

📘 코드

using System.Text;

namespace BOJ
{
    class No_2580
    {
        const int MAX_BOARD_COUNT = 9;
        const int SUM_FROM_ONE_TO_NINE = 45;

        static bool flag = false;
        
        static void Main()
        {
            StringBuilder sb = new StringBuilder();
            List<(int, int)> list = new List<(int, int)>();

            int[,] board = new int[MAX_BOARD_COUNT, MAX_BOARD_COUNT];

            for (int i = 0; i < MAX_BOARD_COUNT; i++)
            {
                int[] inputs = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                for (int j = 0; j < MAX_BOARD_COUNT; j++)
                {
                    board[i, j] = inputs[j];

                    if (board[i, j] == 0)
                    {
                        list.Add((i, j));
                    }
                }
            }
            
            FindBlank(0, board, list);

            for (int i = 0; i < MAX_BOARD_COUNT; i++)
            {
                for (int j = 0; j < MAX_BOARD_COUNT; j++)
                {
                    sb.Append($"{board[i, j]} ");
                }

                sb.AppendLine();
            }

            Console.WriteLine(sb);
        }

        static void FindBlank(int depth, int[,] board, List<(int, int)> list)
        {
            if (depth == list.Count)
            {
                flag = true;
                return;
            }
            
            var cur = list[depth];

            for (int num = 1; num <= MAX_BOARD_COUNT; num++)
            {
                if (IsExistInRow(num, cur.Item1, board)
                    || IsExistInCol(num, cur.Item2, board)
                    || IsExistInBox(num, cur.Item1, cur.Item2, board))
                {
                    continue;
                }
                
                board[cur.Item1, cur.Item2] = num;
                FindBlank(depth + 1, board, list);

                if (flag == true)
                {
                    return;
                }
            }

            board[cur.Item1, cur.Item2] = 0;
        }

        static bool IsExistInRow(int num, int line, int[,] board)
        {
            for (int i = 0; i < MAX_BOARD_COUNT; i++)
            {
                if(num == board[line, i])
                {
                    return true;
                }
            }

            return false;
        }

        static bool IsExistInCol(int num, int line, int[,] board)
        {
            for (int i = 0; i < MAX_BOARD_COUNT; i++)
            {
                if (num == board[i, line])
                {
                    return true;
                }
            }

            return false;
        }

        static bool IsExistInBox(int num, int x, int y, int[,] board)
        {
            int tx = (x / 3) * 3;
            int ty = (y / 3) * 3;

            for (int i = tx; i < tx + 3; i++)
            {
                for (int j = ty; j < ty + 3; j++)
                {
                    if (num == board[i, j])
                    {
                        return true;
                    }
                }
            }

            return false;
        }
    }   
}

📙 오답노트

여러가지 경우의 수가 한 빈 칸에 존재할 수 있는데 백트래킹을 이용하여 탐색하는데 초기화하는 과정에서 기록하였다가 어느 시점에서 초기화할 지 조금 애를 먹은거 같다.

📒 알고리즘 분류

• 백트래킹