[알고리즘 문제 풀기] 스도쿠(2239)

1. 문제 풀이 아이디어

• 백트래킹을 통해 빈 칸에 1~9 숫자를 넣어가며 정답을 찾아 문제를 해결할 수 있다.

2. 나의 정답 코드

using System.Text;
StringBuilder sb = new StringBuilder("");

using (StreamReader sr = new StreamReader(Console.OpenStandardInput()))
    using (StreamWriter sw = new StreamWriter(Console.OpenStandardOutput()))
{
    int[][] s = new int[9][];
    for (int i = 0; i < 9; i++)
    {
        s[i] = new int[9];
        string line = sr.ReadLine();
        for (int j = 0; j < 9; j++)
        {
            s[i][j] = line[j] - '0';
        }
    }
    Solve(0, 0);
    for(int i = 0; i < 9; i++)
    {
        for(int j = 0; j < 9; j++)
        {
            sb.Append(s[i][j]);
        }
        sb.AppendLine();
    }
    sw.Write(sb);

    bool Solve(int x, int y)
    {
        if (x == 9) return true;
        int nx = y == 8 ? x + 1 : x;
        int ny = y == 8 ? 0 : y + 1;
        if (s[x][y] != 0)
        {
            return Solve(nx, ny);
        }
        bool[] chk = new bool[10];
        for (int i = 0; i < 9; i++)
        {
            chk[s[x][i]] = true;
            chk[s[i][y]] = true;
            chk[s[x / 3 * 3 + i / 3][y / 3 * 3 + i % 3]] = true;
        }
        for (int i = 1; i < 10; i++)
        {
            if (chk[i]) continue;
            s[x][y] = i;
            bool result = Solve(nx, ny);
            if (result) return true;
            s[x][y] = 0;
        }
        return false;
    }
}

3. 정리

• s[x][y]가 0이 아니라면 다음 칸으로 넘어간다.

• 1~9 중에서 행, 열, 3x3 칸에 없는 숫자를 찾아서 넣는다.

• 재귀 호출 결과가 참이면 그대로 종료한다.

• 아니라면 다시 0으로 되돌리고 다음 숫자로 시도한다.

• x == 9까지 도달하면 스도쿠가 완성된 것으로 함수에서 빠져나온다.