골랜디 #6 2580번

Published at: 2025-03-24

Last modified at: 2025-03-24

오늘 푼 문제

안녕하세요 한라나입니다.
6번째는 업로드 시간이 좀 빠릅니다.
내일까지인 과제를 하나도 안 했는데, 지금 컨디션이 박살이 나서, 잠깐 자고 하기 전에 우선 골랜디를 하고 자려고 했거든요.

백트래킹!!이라니!!
이건 그냥 구현이잖아… 머리가 혼탁할때 최악의 선택
그래도 골드 4니까 어렵진 않습니다. 상상한 풀이과정이 아니길 바라는 제 마음은 지피티가 없애버렸지만요.

먼저 보드에서 특정 위치에 숫자를 하나 넣었을 때 그것이 스도쿠 규칙에 맞는지 찾는 함수를 하나 만듭니다. 가로, 세로, 3*3에서 같은 수가 있는지 확인하면 돼요.

bool isValid(int x, int y, int num) {
    int i, j;
    for(i=0;i<9;i++) {
        if(board[x][i]==num) return false;
        if(board[i][y]==num) return false;
    }
    x = (x / 3) * 3;
    y = (y / 3) * 3;
    for(i=x;i<x+3;i++) {
        for(j=y;j<y+3;j++) {
            if(board[i][j]==num) return false;
        }
    }
    return true;
}

다음 백트래킹 함수를 만듭니다. (0, 0)부터 (8, 8)까지 돌면서 0인 자리에 1부터 9까지 다 넣어보고, 넣은 채로 본인 함수를 다시 불러와서 맞는 숫자인지 확인한 다음에, 틀리면 false를 내놓아서 이전 단계로 돌아가도록 하면 됩니다.
숫자를 넣을때 그것이 valid한 숫자인지 판단해주시면 됩니다.

int backtrack() {
    int i, j;
    for(i=0;i<9;i++) {
        for(j=0;j<9;j++) {
            if(board[i][j]==0) {
                int k;
                for(k=1;k<10;k++) {
                    if(isValid(i, j, k)) {
                        board[i][j] = k;
                        if(backtrack()) return true;
                        board[i][j] = 0;
                    }
                }
                return false;
            }
        }
    }
    return true;
}

슥삭슥삭입니다. 생각력? 을 쓰는게 귀찮은 문제라 골드 4인가 보네요. 근데 안 그런 백트래킹이 어딨겠습니까?

감사합니다.

---

전체 코드

#include <stdio.h>

//using namespace std;

int board[9][9];

bool isValid(int x, int y, int num) {
    int i, j;
    for(i=0;i<9;i++) {
        if(board[x][i]==num) return false;
        if(board[i][y]==num) return false;
    }
    x = (x / 3) * 3;
    y = (y / 3) * 3;
    for(i=x;i<x+3;i++) {
        for(j=y;j<y+3;j++) {
            if(board[i][j]==num) return false;
        }
    }
    return true;
}

int backtrack() {
    int i, j;
    for(i=0;i<9;i++) {
        for(j=0;j<9;j++) {
            if(board[i][j]==0) {
                int k;
                for(k=1;k<10;k++) {
                    if(isValid(i, j, k)) {
                        board[i][j] = k;
                        if(backtrack()) return true;
                        board[i][j] = 0;
                    }
                }
                return false;
            }
        }
    }
    return true;
}

int main() {
    int i, j;
    for(i=0;i<9;i++) {
        for(j=0;j<9;j++) {
            scanf("%d", &board[i][j]);
        }
    }
    backtrack();
    for(i=0;i<9;i++) {
        for(j=0;j<8;j++) {
            printf("%d ", board[i][j]);
        }
        printf("%d\n", board[i][8]);
    }
    return 0;
}