문제 푼 날짜 : 2021-09-19

문제

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

접근 및 풀이

문제의 제한사항에 아래와 같이 아주 친절하게 백트래킹 알고리즘을 이용하는 문제라고 명시되어있다.

백트래킹 알고리즘으로 풀 수 있는 입력만 주어진다.

사실, 이 문제가 백트래킹으로 분류되어있어서 이미 알고는 있었지만, 모든 문제에 이런 제한사항이 있으면 얼마나 좋을까라는 생각을 잠시나마 해봤다..

아무튼 스도쿠는 아주 유명한 게임이 때문에 규칙은 너무나 유명하기도 해서 문제를 이해하는 데에 큰 어려움은 없었고, 아래의 생각대로 코드를 구현하였다.

1. 주어진 입력에서 빈 칸의 갯수를 세어준다.(입력의 0)
2. 이를 매개변수로 dfs를 구현해준다.
   2-1. 매 빈 칸에 1부터 9까지 넣어보면서 빈 칸이 속한 행과 열, 3x3 정사각형까지 그 숫자가 들어갈 수 있는지 체크해준다.
   2-2. 모든 빈 칸이 조건에 맞게 숫자가 채워지면 바로 return (스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다. 라고 했으므로 더 이상 찾을 필요가 없기 때문이다.)

코드

// 백준 2580번 : 스도쿠
#include <iostream>
#include <vector>

using namespace std;

int board[9][9];
vector<pair<int, int>> pos;
int zero_cnt = 0;

bool canFill(pair<int, int> point) {
    for (int i = 0; i < 9; i++) {
        if (board[point.first][i] == board[point.first][point.second] && i != point.second) {
            return false;
        }
        if (board[i][point.second] == board[point.first][point.second] && i != point.first) {
            return false;
        }
    }
    int row_scope = point.first / 3;
    int col_scope = point.second / 3;

    for (int i = row_scope * 3; i < row_scope * 3 + 3; i++) {
        for (int j = col_scope * 3; j < col_scope * 3 + 3; j++) {
            if (board[i][j] == board[point.first][point.second] && i != point.first && j != point.second) {
                return false;
            }
        }
    }
    return true;
}

bool make_sudoku(int N) {
    if (N == zero_cnt) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                cout << board[i][j] << ' ';
            }
            cout << '\n';
        }
        return true;
    }
    for (int num = 1; num <= 9; num++) {
        board[pos[N].first][pos[N].second] = num;
        if (canFill(pos[N])) {
            if (make_sudoku(N + 1)) {
                return true;
            }
        }
    }
    board[pos[N].first][pos[N].second] = 0;
    return false;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            cin >> board[i][j];
            if (board[i][j] == 0) {
                pos.push_back(make_pair(i, j));
                zero_cnt++;
            }
        }
    }
    make_sudoku(0);

    return 0;
}

결과

피드백

역시 조금만 어려워지니 구현하는데 시간이 오래걸렸다.. 문제를 풀 때 좀 더 집중하자.