백준 2580번 스도쿠 - C++(cpp) 풀이

---

 

1. 백트래킹으로 빈자리를 차례로 채워나간다.
2. 최초 해답을 찾은 이후에는 더 이상 탐색할 필요가 없으므로 모든 탐색을 리턴으로 종료한다.

 

1. 백트래킹으로 빈자리를 차례로 채워나간다.

 백트래킹 문제이다. 빈칸을 차례로 채워나갈 것이다. 아래 코드에서는 왼쪽 위부터 차례로 채웠다. 어떤 빈칸을 채울 때에는 1~9 중 빈칸에 들어갈 수 있는 수들을 전부 넣어본다. 빈칸에 들어갈 수 있는 수는 같은 행, 열, 블록에 있지 않아야 한다.

 

2. 최초 해답을 찾은 이후에는 더 이상 탐색할 필요가 없으므로 모든 탐색을 리턴으로 종료한다.

 모든 칸을 다 채웠다면 해답을 찾은 것이다. 해답을 찾았는지 여부를 bool 전역 변수로 두고, 해답을 찾으면 이 변수에 기록한다. 이후 모든 탐색은 하지 않아도 되므로, 빈칸을 채우는 fill 함수에 해답을 찾았는지 여부를 체크하는 조건문을 두고, 만약 해답을 찾은 이력이 있다면 바로 리턴하여 탐색을 종료하여 필요 없는 탐색을 줄여준다.

반응형

---

#include <iostream>
#include <vector>

using namespace std;

int sudoku[9][9];
bool finish;

bool check(int r, int c, int n) {
    int block_r = r / 3;
    int block_c = c / 3;
    
    for(int i=0; i<9; i++) {
        if (sudoku[r][i] == n) return false;
        if (sudoku[i][c] == n) return false;
        if (sudoku[block_r*3+i/3][block_c*3+i%3] == n) return false;
    }
    
    return true;
}

void fill(int r, int c) {
    if (finish) return;
    
    if (r == 9) {
        finish = true;
        
        for(int i=0; i<9; i++) {
            for(int j=0; j<9; j++) {
                cout << sudoku[i][j] << " ";
            }
            cout << "\n";
        }
        
        return;
    }
    
    int next_r = (r * 9 + c + 1) / 9;
    int next_c = (r * 9 + c + 1) % 9;
    
    if (sudoku[r][c] != 0) {
        fill(next_r, next_c);    
    }
    else {
        for(int i=1; i<=9; i++) {
            if (!check(r, c, i)) continue;
            
            sudoku[r][c] = i;
            fill(next_r, next_c);
            sudoku[r][c] = 0;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    for(int i=0; i<9; i++) {
        for(int j=0; j<9; j++) {
            cin >> sudoku[i][j];
        }
    }
    
    fill(0, 0);

    return 0;
}