[백준 2239] 스도쿠

🔗 알고리즘 문제

알고리즘 스터디 시간에 친구가 풀고 있는 것을 보고 나도 한번 풀어본 문제! 백트래킹에 대해서 공부한지는 얼마되지 않았지만, 새로운 개념을 생각해내는 것이 아닌 구현만 주의해서 차근차근한다면 풀 수 있는 문제기에 풀어낼 수 있었다.

문제 분석

이 문제는 다들 한번씩은 풀어 본 스도쿠를 그대로 코드로 옮기어 컴퓨터가 풀게 하면 되는 문제이다.

발상 & 알고리즘 설계

우선 이 문제는 일단 자리에 들어가는 수를 하나씩 넣어보고 아니라면 다시 돌아가 새로운 수를 넣어가며 진행해야 하기에 백트래킹으로 해결 할 수 있다.

우선 칸에 수가 들어갈 수 있는 조건 체크부터 만들었다.

bool check(int _i, int _j, int num){
	// 열에 같은 숫자가 있는지
    for(int i = 0; i < 9; i++){
        if(board[i][_j] == num)
            return false;
    }
	
    // 행에 같은 숫자가 있는지
    for(int j = 0; j < 9; j++){
        if(board[_i][j] == num)
            return false;
    }

    int box_i = _i / 3 * 3;
    int box_j = _j / 3 * 3;
	
    
    // 3*3 블럭에 같은 숫자가 있는지
    for(int i = box_i; i < box_i + 3; i++) {
        for (int j = box_j; j < box_j + 3; j++) {
            if(board[i][j] == num)
                return false;
        }
    }

    return true;
}

조건 체크는 단순 for문으로 쉽게 구현하였다.

이제 백트래킹을 진행해주면 되는데, 2차원 백트래킹도 1차원과 크게 다르지 않게 구현할 수 있다.

void func(int i, int j){
	// 다음 행으로 넘어가기
    if(j == 9){
        func(i + 1, 0);
        return;
    }
	
    // 모든 행에 숫자를 채웠다면 정답 배열에 복사해주기
    if(i == 9){
        for(int _i = 0; _i < 9; _i++){
            for(int _j = 0; _j < 9; _j++){
                answer[_i][_j] = board[_i][_j];
            }
        }
        return;
    }
	
    // 이미 숫자가 채워져 있다면 다음 열로 이동
    if(board[i][j] != 0){
        func(i, j + 1);
        return;
    }
	
    // 숫자 하나하나 넣어보기
    for(int n = 1; n < 10; n++){
        if(check(i, j, n)){
            board[i][j] = n;
            func(i, j + 1);
            board[i][j] = 0;
        }
    }
}

분명 맞게 구현하였고, 출력도 다 잘 나오는데 제출해보니 시간초과가 나였다.

찬찬히 디버깅을 돌려보니, 모든 행에 숫자를 채웠을 때 정답배열에 계속 깊은복사를 진행하는 부분이 꽤나 많은 시간을 잡는거 같았다.

어쩌피 가장 작은 행렬을 출력하는 것이기에 해당 시점에서 복사가 아닌 바로 출력을 해도 괜찮겠다는 생각이 들었다.

해당 로직으로 수정하고 정답을 받아낼 수 있었다!

코드

#include<iostream>

using namespace std;

int board[9][9] = {};

bool check(int _i, int _j, int num){
    for(int i = 0; i < 9; i++){
        if(board[i][_j] == num)
            return false;
    }

    for(int j = 0; j < 9; j++){
        if(board[_i][j] == num)
            return false;
    }

    int box_i = _i / 3 * 3;
    int box_j = _j / 3 * 3;

    for(int i = box_i; i < box_i + 3; i++) {
        for (int j = box_j; j < box_j + 3; j++) {
            if(board[i][j] == num)
                return false;
        }
    }

    return true;
}

void func(int i, int j){
    if(j == 9){
        func(i + 1, 0);
        return;
    }

    if(i == 9){
        for(int _i = 0; _i < 9; _i++){
            for(int _j = 0; _j < 9; _j++){
                cout << board[_i][_j];
            }
            cout << "\n";
        }
        exit(0);
    }

    if(board[i][j] != 0){
        func(i, j + 1);
        return;
    }

    for(int n = 1; n < 10; n++){
        if(check(i, j, n)){
            board[i][j] = n;
            func(i, j + 1);
            board[i][j] = 0;
        }
    }
}

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

    for(int i = 0; i < 9; i++){
        string line;
        cin >> line;
        for(int j = 0; j < 9; j++){
            board[i][j] = line[j] - '0';
        }
    }

    func(0, 0);
}