문제

문제 링크

어떻게 접근할 것인가?

  • 일단 스도쿠 판을 다 받아옵니다.
  • 백트레킹 함수를 호출합니다.
  • 3*3, 가로, 세로를 쭉 확인해서 1 ~ 9 까지의 숫자 중에 없는 애를 확인합니다. (현명쓰…)
  • 해당 위치에 cnt가 0인 수가 있으면 넣어주고 DFS를 진행합니다.
  • 숫자를 찾을 수 없으면 0을 return하고 백트래킹해줍니다.
  • 판을 숫자로 가득채우면 1을 return합니다.
  • 다 끝나고 출력해줍니다.

코드

#include <cstdio>

typedef struct Point{
    int x, y;
    Point(){

    }
    Point(int i, int j){
        x = i;
        y = j;
    }
}Point;

int n = 0, sudoku[9][9];
Point v[81];

int backtrack(int c){   
    if(c == n) return 1;
    int cnt[10] = {0,};
    int X = v[c].x, Y = v[c].y, result = 0;
    int sx = (X / 3) * 3, sy = (Y / 3) * 3;
    for(int i = sx; i < sx + 3; i++){
        for(int j = sy; j < sy + 3; j++) cnt[sudoku[i][j]] = 1;
    }
    for(int i = 0; i < 9; i++) cnt[sudoku[X][i]] = cnt[sudoku[i][Y]] = 1;
    
    for(int i = 1; i < 10; i++){
        if(cnt[i] == 0) {
            sudoku[X][Y] = i;
            result = backtrack(c+1);
            if(result) break;
            sudoku[X][Y] = 0;
        }
    }
    return result;
}

int main(){
    for(int i = 0; i < 9; i ++){
        for(int j = 0; j < 9; j++){
            scanf("%d", &sudoku[i][j]);
            if(!sudoku[i][j]) v[n++] = Point(i, j);      
        }
    }
    backtrack(0);
    for(int i = 0; i < 9; i++){
        for(int j = 0; j < 9; j++) printf("%d ", sudoku[i][j]);
        printf("\n");
    }
}

느낀점

  • 육목을 했던 경험을 바탕으로 돌을 놨다 뺐다 하는 것을 손쉽게 구현했다.
  • 기분이 아주 좋다아ㅏ~ㅎㅎㅎ
  • 다음 문제도 달려보자!