[백준] 2239 - 스도쿠

2239. 스도쿠 풀이

난이도: Gold IV
문제 주소: https://www.acmicpc.net/problem/2239

문제 풀이

이 문제는 9x9 보드에서 빈칸(0)으로 주어진 부분을 1부터 9까지의 숫자로 규칙에 맞게 채워넣어야 하는 문제이다.

일단 1부터 9까지 하나하나 다 넣어보는 백트래킹 방식을 사용해야지라고는 마음 먹었는데
문제는 0에 지금 이숫자를 넣을수 있는지 를 체크하는거보다 일단 다 채우고 수도쿠가 성립하는지 체크하는 방식으로 갔더니 코드가 끝나질 않아서 풀이 방식을 지금 이 칸에 이 숫자를 넣어도 되는지 체크하는 방식으로 갔다

 

bool solve(int seq)
{
    if (seq == 81) return true;
    int r = seq / 9;
    int c = seq % 9;
    if (sudoku[r][c] != 0 ) return solve(seq + 1);
    for (int i = 1; i <= 9; i++) {
        if (ifCheck(r, c, i)) {
            sudoku[r][c] = i;
            if (solve(seq + 1)) return true;
            sudoku[r][c] = 0;
        }
    }
    return false;
}

풀이의 핵심은 seq라는 변수를 통해 0부터 80까지 총 81개의 칸을 처음부터 하나씩 확인해 나가는 것이다.

만약 현재 확인 중인 칸 sudoku[r][c]가 이미 채워져 있다면(0이 아니라면) 다음 칸을 무사히 탐색해 나갈 수 있으므로 solve(seq + 1)을 통해 바로 넘어가 준다.

 

반대로 현재 칸이 빈칸(0)이라면 1부터 9까지의 숫자를 반복하면서 ifCheck 함수를 사용하여 가로, 세로, 3x3 영역 내에 겹치는 숫자가 없는지 확인한 뒤 조건에 맞는다면 그 값을 현재 칸에 덮어씌운다.

이렇게 하는 이유는 백트래킹 과정에서 현재 칸에 숫자를 임시로 채워보고 이후 탐색에서 조건이 맞지 않으면 다시 0으로 되돌려야 다음 가능성들을 올바르게 탐색할 수 있어지기 때문이다.

 

결과적으로 seq가 81에 도달하게 되면 모든 빈칸을 성공적으로 채웠다는 뜻이므로 true를 반환하고 탐색을 종료하면 완성된 스도쿠의 결과가 바로 나오게 된다. 이렇게 탐색 중 가장 먼저 완성되는 경우가 사전식으로 가장 앞서는 답과 일치하므로 정답을 주어진 시간 안에 구할 수 있어진다.

최종 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <climits>
#include <stack>
#include <unordered_set>

using namespace std;

int sudoku[9][9];
bool ifCheck(int r, int c, int num)
{
    for (int i = 0; i < 9; i++) {
        if (sudoku[r][i] == num || sudoku[i][c] == num) return false;
    }
    int boxRow = (r / 3) * 3;
    int boxCol = (c / 3) * 3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (sudoku[boxRow + i][boxCol + j] == num) return false;
        }
    }
    return true;
}
bool solve(int seq)
{
    if (seq == 81) return true;
    int r = seq / 9;
    int c = seq % 9;
    if (sudoku[r][c] != 0 ) return solve(seq + 1);

    for (int i = 1; i <= 9; i++) {
        if (ifCheck(r, c, i)) {
            sudoku[r][c] = i;
            if (solve(seq + 1)) return true;
            sudoku[r][c] = 0;
        }
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int i = 0; i < 9; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < s.size(); j++) {
            sudoku[i][j] = s[j] - '0';
        }
    }
    solve(0);
    for (int i = 0 ;
        i < 9; i++) {
        for (int j = 0 ; j < 9; j++) {
            cout << sudoku[i][j];
        }
        cout <<"\n";
    }
}   

---

'Algorithm > 백준' 카테고리의 다른 글

[백준] 5525 - IOIOI  (0)	2026.04.12
[백준] 12015 - 가장 긴 증가하는 부분 수열2  (0)	2026.04.08
[백준] 11404 - 플로이드  (0)	2026.04.03
[백준] 9663 N－Queen  (0)	2026.04.01
[백준] 10814 - 나이순 정렬  (0)	2026.04.01