백준 2580번 스도쿠

문제 링크입니다: https://www.acmicpc.net/problem/2580

흥미로운 백트래킹 문제였습니다.

처음에 풀 때는 3*3 칸 내에서도 1~9가 하나씩 존재해야한다는 규칙을 잊어먹어서 틀렸습니다.

3*3 칸 내 인덱스는 change2SquareIdx 함수를 통해 반환받았고 각 열, 행, 그리고 3*3 칸 내에 숫자 존재 여부를 파악하기 위해 bool 형 배열 row, col, square를 선언했습니다.

스도쿠는 총 9 * 9 = 81칸이기 때문에 DFS 함수를 최초로 호출할 때 매개변수로 0을 전달하고 cnt가 81이 되면 스도쿠 판을 출력하는 식으로 코드를 작성했습니다.

주의할 점은, 스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다는 것입니다!(exit(0) 필수)

*exit(-1) 할 경우 런타임 에러납니다...

#include <iostream>

#include <vector>

using namespace std;

 

const int MAX = 9;

 

int sudoku[MAX][MAX];

bool row[MAX][MAX + 1]; //열, 1~9

bool col[MAX][MAX + 1]; //행, 1~9

bool square[MAX][MAX + 1]; //3*3 박스 idx, 1~9

 

int change2SquareIdx(int y, int x)

{

        return (y / 3) * 3 + x / 3;

}

 

void DFS(int cnt)

{

        if (cnt == 81) //Sudoku는 총 81칸

        {

                 for (int i = 0; i < MAX; i++)

                 {

                         for (int j = 0; j < MAX; j++)

                                 cout << sudoku[i][j] << " ";

                         cout << endl;

                 }

                 exit(0); //답을 하나만 출력

        }

 

        int y = cnt / 9;

        int x = cnt % 9;

 

        if (sudoku[y][x]) //칸이 채워져있으면

                 DFS(cnt + 1);

        else //채워져있지 않았고

        {

                 for (int k = 1; k <= MAX; k++)

                 {

                         //sudoku 규칙에 적합하면 채우고 본다

                         if (!col[x][k] && !row[y][k] && !square[change2SquareIdx(y, x)][k])

                         {

                                 sudoku[y][x] = k;

                                 col[x][k] = true;

                                 row[y][k] = true;

                                 square[change2SquareIdx(y, x)][k] = true;

                                 DFS(cnt + 1);

                                 sudoku[y][x] = 0;

                                 col[x][k] = false;

                                 row[y][k] = false;

                                 square[change2SquareIdx(y, x)][k] = false;

                         }

                 }

        }

}

 

int main(void)

{

        for (int i = 0; i < MAX; i++)

        {

                 for (int j = 0; j < MAX; j++)

                 {

                         cin >> sudoku[i][j];

                         if (sudoku[i][j])

                         {

                                 col[j][sudoku[i][j]] = true;

                                 row[i][sudoku[i][j]] = true;

                                 square[change2SquareIdx(i, j)][sudoku[i][j]] = true;

                         }

                 }

        }

 

        DFS(0); //sudoku는 81칸

 

        return 0;

}

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~