[BOJ알고리즘,C++]#2580_스도쿠, 백트래킹, DFS

#1. 문제

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

 

---

 

#2. 풀이

 

1. 백트래킹

[알고리즘]#6_백 트래킹

백 트래킹은 최적 해를 찾기 위해 여러 후보 경로를 점진적으로 탐색하며, 현재 경로가 최적 해로 이어질 수 없다고 판단되면 이전 단계로 돌아가 다른 후보 경로들을 탐색하는 방법입니다. 

 

2. '빈칸'에 대해서만 백 트래킹, 가로/세로/3x3 체크

1. 먼저, 9x9 보드판을 구성하고, 빈칸 정보를 별도의 vector <pair <int, int>> 형식에 저장해 둡니다. 
2. 백트래킹을 위한 DFS를 정의합니다. 먼저, 종료 조건은 모든 빈 칸이 채워졌을 경우입니다. 따라서, 각 빈칸에 1~9 숫자를 넣고 해당 빈칸이 속한 가로, 세로, 3x3 박스의 조건 만족 여부를 체크하고, 이를 만족한다면 다음 빈칸에 대하여 DFS를 수행하는 방식으로 구현합니다.

 

---

 

#3. 코드

/*
    @링크: https://www.acmicpc.net/problem/2580
*   @문제: 스도쿠, 행, 열에 1~9 사이의 숫자를 한 번씩만 사용하여 스도쿠 완성
*   @설명
        1. 9x9 보드 구성 시 빈 칸의 좌표 기억
        2. 각 빈 칸에 대하여 1~9를 넣어보며, 완성도 평가 및 백트래킹 수행
        3. 빈 칸이 속해 있는 COL, ROW, 3x3 보드의 완성도만 평가해준다.
*/

#include <iostream>
#include <vector>
using namespace std;

#define MAX 9

vector<vector<int>> board(MAX, vector<int>(MAX, 0));
vector<pair<int,int>> blanks;

bool isValid(int row, int col, int num) {
    // 행 검사
    for (int i = 0; i < MAX; i++)
        if (board[row][i] == num) return false;
    
    // 열 검사
    for (int i = 0; i < MAX; i++)
        if (board[i][col] == num) return false;
    
    // 3x3 박스 검사
    int startRow = row - row % 3, startCol = col - col % 3;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            if (board[i + startRow][j + startCol] == num) return false;
    
    return true;
}

// @백트래킹
bool solve(int idx) {
    if (idx == blanks.size()) return true;
    
    int row = blanks[idx].first, col = blanks[idx].second;
    for (int num = 1; num <= 9; num++) {
        if (isValid(row, col, num)) {
            board[row][col] = num;
            if (solve(idx + 1)) return true;
            board[row][col] = 0;
        }
    }
    return false;
}

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

    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            cin >> board[i][j];
            if (board[i][j] == 0) blanks.push_back({i, j});
        }
    }

    solve(0);

    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            cout << board[i][j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}

 

 

---