백준[2580] - 스도쿠

문제

백준 2580 문제 보기

접근 방법

백트래킹을 활용해서 문제를 풀수 있다.

• 입력받은 값들 중 빈 좌표를 따로 저장
• 첫번째 저장된 좌표에 1~9까지 숫자를 대입하여 현재 스도쿠를 만족하는지 검사
• 만족한다면 다음 좌표에서 1~9까지 숫자를 대입하고 검사를 반복

코드

#include <iostream>
#include <vector>
#include <utility>
#include <cstdlib>

using namespace std;

int sudoku[9][9];
vector<pair<int, int>> arr;
// 똑같은 숫자가 있는지 세로 검사
bool chk_vertical(int c, int num) {
    for(int r = 0; r < 9; r ++) {
        if(sudoku[r][c] == num) {
            return false;
        }
    }
    return true;
}
// 가로 검사
bool chk_horizontal(int r, int num) {
    for(int c = 0; c < 9; c ++) {
        if(sudoku[r][c] == num) {
            return false;
        }
    }
    return true;
}
// 3*3 네모난 모양 검사
bool chk_square(int r, int c, int num) {
    r = r / 3;
    c = c / 3;
    for(int rr = r * 3; rr < (r * 3) + 3; rr ++) {
        for(int cc = c * 3 ; cc < (c * 3) + 3; cc ++) {
            if(sudoku[rr][cc] == num) {
                return false;
            }
        }
    }
    return true;
}

void dfs(int idx) {
    // 모든 좌표에 숫자를 넣었다면 정답 출력
    if(idx == arr.size()) {
        for(int i = 0; i < 9; i ++) {
            for(int j = 0; j < 9; j ++) {
                cout << sudoku[i][j] << " ";
            }
            cout << "\n";
        }
        exit(0);
    }
    // 1~9까지 숫자를 넣음
    for(int num = 1; num <= 9; num ++) {
        int r = arr[idx].first;
        int c = arr[idx].second;
        // 가로, 세로, 네모 모양을 검사해서 해당 숫자가 들어갈 수 있는지 확인
        if(chk_vertical(c, num) && chk_horizontal(r, num) && chk_square(r, c, num)) {
            // 들어갈 수 있다면 숫자를 넣음
            sudoku[r][c] = num;
            // 다음 좌표로 이동
            dfs(idx + 1);
            // 원상 복구
            sudoku[r][c] = 0;
        }
    }
}

int main() {
    for(int i = 0; i < 9; i ++) {
        for(int j = 0; j < 9; j ++) {
            cin >> sudoku[i][j];
            // 비어있는 칸은 좌표를 따로 저장
            if(sudoku[i][j] == 0) {
                arr.push_back({ i, j });
            }
        }
    }
    // 1~9까지 숫자를 넣음
    for(int num = 1; num <= 9; num ++) {
        int r = arr[0].first;
        int c = arr[0].second;
       // 가로, 세로, 네모 모양으로 해당 num이 들어갈 수 있는지 확인
       if(chk_vertical(c, num) && chk_horizontal(r, num) && chk_square(r, c, num)) {
           sudoku[r][c] = num;
           dfs(1);
           sudoku[r][c] = 0;
       }
    }
    return 0;
}