[백준/C,C++] 2580번: 스도쿠

www.acmicpc.net/problem/2580

2580번: 스도쿠

백준 단계별로 풀어보기 백트래킹 문제 중에서 가장 어려웠던 문제입니다. 이 문제는 노드를 선택하고 한참 노드를 선택하다 선택할 수 있는 노드가 없다면 다시 계속 선택할 수 있는 노드가 있는 부모 노드로 되돌아가야 합니다. 머리로 계속 로직을 떠올려보았지만 쉽지 않았는데 dfs 함수에 return 한 줄을 넣는 것으로 해결되었습니다.

void sudoku(int cnt)
{
    int row, col;
    if (cnt == blanks) {
        complete = true;
        return;
    }
    row = zero[cnt].first;
    col = zero[cnt].second;
    for (int num = 1; num < SIZE; num++) {
        if (isPossible(row, col, num)) {
            board[row][col] = num;
            sudoku(cnt + 1);
            if (complete) return;
        }
    }
    board[row][col] = 0;
    return;
}

sudoku(dfs) 함수를 먼저 살펴보면 조건 검사 이후 다음 노드를 선택하며 계속 자기 자신을 재귀 호출하는 형태입니다. 여기서 반복문 이후의 코드가 중요한데, 다음 노드를 탐색하는 과정에서 조건에 맞는 노드가 단 하나도 없을 경우 자기를 호출했던 곳으로 다시 리턴해야합니다. 이 부분을 간과해서 코드를 짜는데 조금 헤맸습니다.

bool isPossible(int row, int col, int num)
{
    for (int i = 1; i < SIZE; i++) {
        if (board[row][i] == num && board[row][i] != 0) return false;
        if (board[i][col] == num && board[i][col] != 0) return false;
    }
    int r = ((row - 1) / 3) * 3 + 1;
    int c = ((col - 1) / 3) * 3 + 1;
    for (int i = r; i < r + 3; i++) {
        for (int j = c; j < c + 3; j++) {
            if (board[i][j] == num && board[i][j] != 0) return false;
        }
    }
    return true;
}

조건에 사용되는 함수는 비교적 단순한 로직으로 이루어져 있습니다. 같은 행, 같은 열, 작은 사각형(3x3)안에 같은 수가 있는지 확인만 해주면 됩니다.

#include<iostream>
#include<vector>

using namespace std;

#define SIZE 10

int board[SIZE][SIZE];
bool complete = false;
vector<pair<int, int>>zero;
int blanks = 0;

bool isPossible(int row, int col, int num)
{
    for (int i = 1; i < SIZE; i++) {
        if (board[row][i] == num && board[row][i] != 0) return false;
        if (board[i][col] == num && board[i][col] != 0) return false;
    }
    int r = ((row - 1) / 3) * 3 + 1;
    int c = ((col - 1) / 3) * 3 + 1;
    for (int i = r; i < r + 3; i++) {
        for (int j = c; j < c + 3; j++) {
            if (board[i][j] == num && board[i][j] != 0) return false;
        }
    }
    return true;
}

void sudoku(int cnt)
{
    int row, col;
    if (cnt == blanks) {
        complete = true;
        return;
    }
    row = zero[cnt].first;
    col = zero[cnt].second;
    for (int num = 1; num < SIZE; num++) {
        if (isPossible(row, col, num)) {
            board[row][col] = num;
            sudoku(cnt + 1);
            if (complete) return;
        }
    }
    board[row][col] = 0;
    return;
}

int main(void)
{
    for (int i = 1; i < SIZE; i++) {
        for (int j = 1; j < SIZE; j++) {
            cin >> board[i][j];
            if (board[i][j] == 0) {
                zero.push_back(pair(i, j));
            }
        }
    }

    blanks = zero.size();

    sudoku(0);

    for (int i = 1; i < SIZE; i++) {
        for (int j = 1; j < SIZE; j++) {
            cout << board[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

입력값 중 0인 값만 vector에 push한 후 dfs 함수를 실행시켜주면 됩니다.