[C++] 2239번 스도쿠 - 구현, 백트래킹

#include <iostream>

#define LOOP(i, N) for(int i=1; i<=N; i++)
#define MAX 10

using namespace std;

char matmp[MAX][MAX];
int ma[MAX][MAX];  //스도쿠 배열
bool col[MAX][MAX], row[MAX][MAX], box[MAX][MAX];  //확인용 메모

void input()
{
    LOOP(i, 9) {
        LOOP(j, 9) {
            cin >> matmp[i][j];
            ma[i][j]=matmp[i][j] - '0';
            
            int v = ma[i][j];
        
            col[j][v]=row[i][v]=box[(i-1)/3*3 + (j-1)/3][v]=1;
        }
    }
}

void backtracking(int cnt)
{
    if(cnt == 82) {  //도착하면 출력 후 종료
        LOOP(i, 9) {
            LOOP(j, 9) cout << ma[i][j];
            cout << '\n';
        }
        exit(0);
    }
    
    int x = (cnt-1)/9+1;
    int y = (cnt-1)%9+1;
    
    if(ma[x][y])  //값이 있으면 넘어가기
        backtracking(cnt+1);
    else {
        LOOP(i, 9) {
            if(!row[x][i] && !col[y][i] && !box[(x-1)/3*3 + (y-1)/3][i]) {  //백트래킹 조건
                row[x][i]=col[y][i]=box[(x-1)/3*3 + (y-1)/3][i]=1;
                ma[x][y]=i;
                backtracking(cnt+1);
                row[x][i]=col[y][i]=box[(x-1)/3*3 + (y-1)/3][i]=0;
                ma[x][y]=0;
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    input();
    
    backtracking(1);
    
    return 0;
}

너무 어려웠다. 사실 백트래킹을 많이 접해보지 않아서이기도 하다. 특히 좌표를 1부터 잡으니까 너무 많이 헷갈려서 오래걸렸던 것도 있는 것 같다. 이 문제 푸는데 너무 힘빠져서...

 

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.