← 문제 풀이 목록

백준 2580: 스도쿠

/ 12분 분량 / 문제 풀이
#알고리즘#백준#코딩테스트

Gold IV 난이도의 스도쿠 문제를 C++로 풀이한 내용입니다. 주어진 빈 스도쿠 판을 완성하는 알고리즘을 구현하는 문제입니다.

백준 2580: 스도쿠

Gold IV 난이도의 스도쿠 문제를 C++로 풀이한 내용입니다. 주어진 빈 스도쿠 판을 완성하는 알고리즘을 구현하는 문제입니다.

문제 소개

  • 문제 번호: 2580
  • 문제명: 스도쿠
  • 난이도 (티어): Gold IV
  • 사용 언어: C++
  • 실행 시간: 236 ms
  • 메모리: 2020 KB
  • 문제 요약: 9x9 크기의 스도쿠 판이 주어집니다. 일부 칸은 숫자가 채워져 있고, 일부 칸은 비어 있습니다 (0으로 표시). 스도쿠 규칙에 맞게 빈칸을 모두 채워 완성된 스도쿠 판을 출력해야 합니다. 스도쿠 규칙은 다음과 같습니다:
    1. 각 행에는 1부터 9까지의 숫자가 중복 없이 들어가야 합니다.
    2. 각 열에는 1부터 9까지의 숫자가 중복 없이 들어가야 합니다.
    3. 9개의 3x3 격자 (블록) 각각에는 1부터 9까지의 숫자가 중복 없이 들어가야 합니다.

접근 방법

이 문제는 전형적인 백트래킹(Backtracking) 알고리즘을 사용하여 해결할 수 있습니다. 스도쿠 판을 완성하기 위해 빈칸을 하나씩 채워나가되, 숫자를 넣을 때마다 스도쿠 규칙에 위배되는지 확인합니다. 만약 규칙에 위배된다면 해당 숫자는 포기하고 다른 숫자를 시도합니다. 규칙에 맞는 숫자를 찾지 못하면 이전 단계로 돌아가 잘못된 선택을 수정합니다.

왜 백트래킹인가?

  • 탐색 공간: 스도쿠는 매우 넓은 탐색 공간을 가집니다. 모든 빈칸에 대해 1부터 9까지의 숫자를 대입해보는 것은 비효율적입니다.
  • 제약 조건: 스도쿠의 규칙은 강력한 제약 조건입니다. 이 제약 조건을 활용하여 잘못된 경로는 빠르게 탐색에서 제외할 수 있습니다.
  • 깊이 우선 탐색 (DFS) 의 원리: 백트래킹은 DFS의 한 형태로, 가능한 모든 경로를 탐색하되, 특정 조건(여기서는 스도쿠 규칙)에 맞지 않는 경우 해당 경로는 더 이상 탐색하지 않고 이전 상태로 되돌아갑니다.

풀이 과정

  1. 스도쿠 판 초기화: 입력받은 9x9 스도쿠 판을 2차원 배열 board에 저장합니다. 0은 빈칸을 의미합니다.

  2. possible(r, c, x) 함수: 특정 위치 (r, c)에 숫자 x를 넣을 수 있는지 검사하는 함수입니다.

    • 가로 검사: r행의 다른 칸에 x가 이미 있는지 확인합니다.
    • 세로 검사: c열의 다른 칸에 x가 이미 있는지 확인합니다.
    • 3x3 격자 검사: (r, c)가 속한 3x3 격자에 x가 이미 있는지 확인합니다. sr = (r / 3) * 3, sc = (c / 3) * 3을 이용하여 해당 격자의 시작 행과 열을 계산합니다.
    • 세 가지 검사 중 하나라도 통과하지 못하면 false를 반환하고, 모두 통과하면 true를 반환합니다.

  3. solve() 함수 (백트래킹): 스도쿠 판을 재귀적으로 완성하는 핵심 함수입니다.

    • 빈칸 찾기: 9x9 판을 순회하며 빈칸 (board[i][j] == 0)을 찾습니다.
    • 기저 사례 (Base Case): 빈칸을 더 이상 찾지 못하면, 스도쿠 판이 모두 채워진 것이므로 true를 반환합니다.
    • 재귀 호출: 빈칸 (i, j)를 찾았다면, 1부터 9까지의 숫자 x에 대해 다음을 시도합니다.
      • possible(i, j, x)를 호출하여 x를 (i, j)에 넣을 수 있는지 확인합니다.
      • 만약 가능하다면, board[i][j] = x로 숫자를 채웁니다.
      • solve() 함수를 재귀적으로 호출하여 다음 빈칸을 채우도록 합니다.
      • 만약 재귀 호출이 true를 반환하면, 모든 과정이 성공적으로 완료된 것이므로 현재 solve() 호출도 true를 반환하며 종료합니다.
      • 만약 재귀 호출이 false를 반환하면, 현재 선택한 x가 결국 잘못된 선택이었음을 의미합니다. 따라서 board[i][j] = 0으로 원래대로 되돌리고(백트래킹), 다음 숫자 x+1을 시도합니다.
    • 실패 처리: 1부터 9까지의 모든 숫자를 시도했음에도 불구하고 빈칸 (i, j)를 채울 수 없다면, 현재 상태로는 스도쿠를 완성할 수 없다는 의미이므로 false를 반환합니다.

  4. main() 함수:

    • 입력 속도 향상을 위해 ios::sync_with_stdio(false); cin.tie(NULL);를 사용합니다.
    • 스도쿠 판을 입력받습니다.
    • solve() 함수를 호출하여 스도쿠를 완성합니다.
    • 완성된 스도쿠 판을 출력합니다.

코드 설명

#include <bits/stdc++.h>
using namespace std;

// 전역 보드: 모든 재귀 호출에서 공유되는 실제 상태
int board[9][9];

// (r, c) 위치에 x를 넣을 수 있는지 검사
bool possible(int r, int c, int x) {
    // 가로 검사: 같은 행에 x가 있으면 넣을 수 없음
    for (int j = 0; j < 9; j++)
        if (board[r][j] == x) return false;

    // 세로 검사: 같은 열에 x가 있으면 넣을 수 없음
    for (int i = 0; i < 9; i++)
        if (board[i][c] == x) return false;

    // 3x3 격자 검사
    int sr = (r / 3) * 3;
    int sc = (c / 3) * 3;
    for (int i = sr; i < sr + 3; i++)
        for (int j = sc; j < sc + 3; j++)
            if (board[i][j] == x) return false;

    return true; // 겹치는 수 없음 → 넣을 수 있음
}

// 스도쿠 완전 탐색 + 백트래킹
bool solve() {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == 0) { // 빈칸 발견
                // 1~9개의 자식 노드 발생
                for (int x = 1; x <= 9; x++) {
                    if (possible(i, j, x)) { // 9개 중 가능한 노드들만 추리기
                        board[i][j] = x; // 3개 남았다 치면 그 3개만 자식노드로 분기
                        
                        if (solve()) return true; // 이번 자식 노드도 또 같은 원리로 분기
                        
                        board[i][j] = 0; // 그 자식노드들이 끝에 가서 결국 잘못된 수 선택이었다면 원상복구
                        
                        // 이후 다음 자식 노드를 분기시켜 본다
                    }
                }
                return false;
            }
        }
    }
    // 모든 칸이 채워짐 → 정답 발견
    // → 마지막 빈칸까지 모순 없이 채워진 유일한 세계선이 board에 남음
    // → 연쇄 true 반환을 통해 모든 부모 호출에서도 선택 확정
    // → solve()가 반환하는 false가 없으므로 이전 선택들이 되돌려지지 않고 그대로 유지
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    // 보드 입력
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
            cin >> board[i][j];

    // 재귀 호출 시작
    // 전역 보드를 직접 수정하며, 각 재귀 호출은
    // 자신이 선택한 수들로 모순이 생기면 false 반환 → 그 때까지 가정한 수들 전부 초기화 -> 다음 자식노드로 분기(수 선택) 시도
    // 마지막까지 모순 없이 채워지면 연쇄 true 반환 → 선택 확정
    solve();

    // 완성된 보드 출력
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++)
            cout << board[i][j] << " ";
        cout << "\n";
    }
}

주요 부분 설명:

  • board[9][9]: 스도쿠 판을 저장하는 전역 2차원 배열입니다. 재귀 함수 간에 공유되어 상태를 관리합니다.
  • possible(int r, int c, int x): (r, c) 위치에 x를 넣는 것이 스도쿠 규칙(가로, 세로, 3x3 격자)에 위배되지 않는지 확인하는 핵심 검증 함수입니다.
  • solve(): 백트래킹의 핵심 로직을 담고 있습니다.
    • 빈칸을 찾으면 1부터 9까지 숫자를 시도합니다.
    • possible 함수로 유효성을 검증한 후, 유효하면 해당 숫자를 넣고 다음 빈칸을 채우기 위해 재귀 호출합니다.
    • 재귀 호출이 성공하면(true 반환) 그대로 진행하고, 실패하면(false 반환) 숫자를 원래대로 되돌리고(board[i][j] = 0) 다른 숫자를 시도하는 백트래킹 과정을 수행합니다.
    • 모든 빈칸을 성공적으로 채우면 true를 반환하며 종료됩니다.
  • main(): 입력 처리, solve() 함수 호출, 결과 출력의 역할을 합니다. ios::sync_with_stdio(false); cin.tie(NULL);는 입력/출력 속도를 개선합니다.

복잡도 분석

  • 시간 복잡도: 최악의 경우, 각 빈칸에 대해 1부터 9까지의 숫자를 모두 시도해볼 수 있습니다. 스도쿠에는 최대 81개의 칸이 있고, 각 칸에 대해 9개의 숫자를 고려해야 합니다. 그러나 possible 함수를 통해 유효하지 않은 탐색 가지는 빠르게 제거됩니다. 이론적으로 최악의 시간 복잡도는 매우 높지만, 실제 스도쿠 문제의 제약 조건 덕분에 훨씬 효율적으로 동작합니다. 대략적으로 O(9^(N*M))으로 표현될 수 있으나, 스도쿠에서는 N=M=9이며, 실제로는 훨씬 적은 수의 탐색으로 완료됩니다.
  • 공간 복잡도: 재귀 호출 스택 깊이가 최대 81 (빈칸의 개수)까지 갈 수 있으므로, O(N*M) 또는 O(81)이 됩니다. 또한, board 배열을 저장하는 데 O(N*M)의 공간이 필요합니다. 따라서 총 공간 복잡도는 O(N*M)으로 볼 수 있습니다.

배운 점

이 문제를 통해 백트래킹 알고리즘의 강력함을 다시 한번 체감할 수 있었습니다.

  • 재귀와 백트래킹의 활용: 복잡한 탐색 문제를 해결할 때 재귀 호출과 백트래킹이 어떻게 효과적으로 사용될 수 있는지 배웠습니다. '시도 -> 검증 -> 재귀 -> 되돌리기'의 패턴을 이해하는 것이 중요합니다.
  • 제약 조건의 중요성: 스도쿠의 규칙과 같은 제약 조건을 possible 함수로 명확하게 정의하고 활용함으로써, 탐색 공간을 크게 줄일 수 있다는 것을 알게 되었습니다.
  • 구현 디테일: 전역 변수 사용, 재귀 함수 내에서의 상태 복구(백트래킹) 등 구현 시 주의해야 할 디테일들을 익혔습니다.

이러한 백트래킹 기법은 스도쿠뿐만 아니라 N-Queens 문제, 미로 찾기, 그래프 탐색 등 다양한 문제에 응용될 수 있습니다.