[백준 / BOJ] - 2580번 스도쿠 C++ 풀이 및 반례 모음

---

 

백준 - 단계별로 풀어보기 [2580] 

https://www.acmicpc.net/problem/2580

문제

 

 

풀이

 

스도쿠는 각 행과 열, 그리고 3x3크기의 구역 9개에 각각 1~9 까지의 숫자가 단 한번씩만 들어가야하는 규칙을 가지고 있다. 

따라서 해당 문제를 풀이하기 위해서는 스도쿠가 유효한지 체크하는 check함수가 필요하고, check함수는

같은 행 또는 열에 혹시 같은 숫자가 있는지, 3x3크기의 구역에 같은 숫자가 있는지를 체크해주는 함수가 될 것이다.

 

그 후, 백트래킹을 통해서 0이 입력된 빈칸 부분에 1부터 9까지의 숫자를 차례로 넣어보고, 모든 칸을 채웠을 때 

결과를 호출하면 되는 문제이다.

 

자세한 풀이는 코드와 주석을 참고하자.

 

코드

 

#include <iostream>
#include <utility>
#include <vector>
using namespace std;
int board[9][9]; // 스도쿠 보드 선언
vector<pair<int, int>> points; // 빈칸의 위치 저장
int cnt = 0;
bool found = false; // 스도쿠 판 완성 플래그
bool check(pair<int, int> p)
{
    int square_x = p.first / 3; // 구역을 나눔
    int square_y = p.second / 3;
    for(int i = 0; i < 9; i++)
    {
        if(board[p.first][i] == board[p.first][p.second] && i != p.second) 
            return false; // 같은 행에 같은 숫자가 있으면 false 반환
        if(board[i][p.second] == board[p.first][p.second] && i != p.first)
            return false; // 같은 열에 같은 숫자가 있으면 false 반환
    }
    for(int i = 3*square_x; i < 3*square_x+3; i++)
        for(int j = 3*square_y; j < 3*square_y+3; j++)
        {
            if(board[i][j] == board[p.first][p.second])
            {
                if(i != p.first && j != p.second)
                    return false; // 같은 구역에 같은 숫자가 있으면 false 반환
            }
        }
    return true; // 모든 조건 만족시 유효성 검사 통과
}
void sudoku(int N) {
    if(N == cnt) // 빈칸의 개수만큼을 채워서 스도쿠 판이 완성되면
    {
        for(int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++)
                cout << board[i][j] << ' ';
            cout << '\n';
        } // 결과 출력
        found = true; // 플래그 true로 변경
        return;
    }
        for(int j = 1; j <= 9; j++)
        {
            board[points[N].first][points[N].second] = j; // 1~9 까지의 숫자를 넣어봄
            if(check(points[N])) // 결과가 유효하면 다음 빈칸을 채우러 감
                sudoku(N+1);
            if(found) // 스도쿠가 완성됬을경우 더 이상 다른 해를 찾을 필요가 없으므로 함수 종료
                return;
        }
    board[points[N].first][points[N].second] = 0;// 최적해를 못찾았을 경우 값 비워주기
     return;
}
int main() {
    pair<int, int> point;
    for(int i = 0; i < 9; i++)
        for(int j = 0; j < 9; j++)
        {
            cin >> board[i][j];
            if(board[i][j] == 0)
            {
                cnt++;
                point.first = i;
                point.second = j;
                points.push_back(point); // 빈칸의 좌표 저장
            }
        }
    sudoku(0);
}

 

평가

 

해당 문제는 30%라는 매우 낮은 정답률을 기록하고 있는데, 그 이유는 시간 초과 에러가 뜬다는점,

그리고 테스트 케이스가 너무 적어, 문제에서 제시된 테스트 케이스 외의 반례가 많이 발생한다는 점에 있다.

 

자신의 코드가 왜 오답인지 이해가 안되시는 분들을 위해 대표적인 반례 테스트케이스 2가지를 정리해보았다.

 

반례(테스트 케이스)

 

TEST CASE # 1

 

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

 

SAMPLE ANSWER #1

 

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 1 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 9 7 2 1 4 3 6 5
5 3 1 6 4 2 9 7 8
6 4 2 9 7 8 5 3 1
9 7 8 5 3 1 6 4 2

 

TEST CASE # 2

 

0 2 0 9 0 5 0 0 0

5 9 0 0 3 0 2 0 0

7 0 0 6 0 2 0 0 5

0 0 9 3 5 0 4 6 0

0 5 4 0 0 0 7 8 0

0 8 3 0 2 7 5 0 0

8 0 0 2 0 9 0 0 4

0 0 5 0 4 0 0 2 6

0 0 0 5 0 3 0 7 0

 

SAMPLE ANSWER # 2

 

3 2 1 9 7 5 6 4 8
5 9 6 8 3 4 2 1 7
7 4 8 6 1 2 9 3 5
1 7 9 3 5 8 4 6 2
2 5 4 1 9 6 7 8 3
6 8 3 4 2 7 5 9 1
8 1 7 2 6 9 3 5 4
9 3 5 7 4 1 8 2 6
4 6 2 5 8 3 1 7 9