6주차 - Backtracking (백준 2580번)

Backtracking

: 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다.
(최적화 문제와 결정 문제를 푸는 방법)

: 모든 경우가 아닌 제약 조건에 맞는 후보해에 대해서만 탐색한다.
 즉, 불필요한 탐색을 하지 않고 이전 단계로 돌아와 다른 후보해를 탐색한다.

해를 찾다가, 지금의 경로가 해가 될 것 같지 않으면, 그 경로로 가지 않고 바로 되돌아간다.
(즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적)

이를 가지치기라고 하는데, 불필요한 부분은 빼고 최대한 올바른 쪽으로 간다는 의미이다.
일반적으로, 불필요한 경로를 조기에 차단할 수 있게 되어 경우의 수가 줄어들지만, 만약 N!의 경우의 수를 가진 문제에서 최악의 경우에는 여전히 지수함수 시간을 필요로 하므로 처리가 불가능 할 수도 있다.
가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다.

---

백준 2580번: 스도쿠

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

2580번: 스도쿠

문제

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

---

#include <iostream>
using namespace std;

int sudoku[10][10];
bool check_row[10][10]; // 행 검사 : x행에 숫자 y가 있으면 true
bool check_col[10][10]; // 열 검사 : x열에 숫자 y가 있으면 true
bool check_square[10][10]; // 작은 정사각형 검사 : x번째 작은 정사각형에 숫자 y가 있으면 true

// row행 col열이 속하는 작은 정사각형 구하기
int get_square(int row, int col){
    return (row/3)*3 + (col/3);
}

// sudoku 출력하기
void print(){
    for(int i=0; i<9; i++){
        for(int j=0; j<9; j++){
            cout << sudoku[i][j] << ' ';
        }
        cout << '\n';
    }
}

// n번째 스도쿠 구하기
bool solve(int n){
    // 마지막 칸인 경우 -> 출력 후 종료
    if(n == 81) {
        print();
        return true;
    }   
    // 행, 열 구하기
    int x = n/9; 
    int y = n%9;
    
    if(sudoku[x][y] != 0) // 수가 있으면 -> 다음 수로 넘어가기
        return solve(n+1);
    else { // 수가 없으면 -> 1~9 검사해서 수 채우기
        for(int i=1; i<=9; i++){
            if(!check_row[x][i] && !check_col[y][i] && !check_square[get_square(x, y)][i]){
                // 스도쿠 처리
                check_row[x][i] = true;
                check_col[y][i] = true;
                check_square[get_square(x, y)][i] = true;
                sudoku[x][y] = i;
                
                if(solve(n+1))
                    return true;
                
                // 다시 돌려놓기 (백트래킹)
                check_row[x][i] = false;
                check_col[y][i] = false;
                check_square[get_square(x, y)][i] = false;
                sudoku[x][y] = 0;
            }
        }
    }
    return false;
}

int main(void){
    
    for(int i=0; i<9; i++){
        for(int j=0; j<9; j++){
            cin >> sudoku[i][j];
            
            // 빈칸이 아닌 경우 처리
            if(sudoku[i][j] != 0){
                check_row[i][sudoku[i][j]] = true;
                check_col[j][sudoku[i][j]] = true;
                check_square[get_square(i, j)][sudoku[i][j]] = true;
            }
        }
    }
    
    // 0번 칸부터 채우기 시작
    solve(0);
    return 0;
}

처음 문제를 봤을 때 풀기 막막해서 구글링을 통해 코드를 참고하며 풀었다. 우선 해당 문제는 백트래킹을 이용하여 푸는 것이 가장 적합하다. 찾아보니 vector를 사용해서 푼 코드가 많았는데, 나는 vector 사용법을 정확히 기억하고 있지 않기 때문에 2차원 배열, 행렬을 만들어 문제를 풀었다.

다른 코드를 참고해서 다른 때보다 쉽게 성공했다!