[ 백준 2580 ] 스도쿠 (C++) - 백트래킹, DFS

---

🔗 문제 링크

2580번: 스도쿠

---

💡 문제 풀이 및 해석

1. 모든 data를 받아올 때, 빈칸(0)만 따로 받아온다.
2. 빈칸에 숫자 1~9가 들어갈 수 있는지 판별한다. (가로, 세로, 섹터)
   2-1. 넣을 수 있다면 넣은 다음 다음 칸으로 넘어간다.
   2-2. 아무 숫자도 넣을 수 없다면 변경사항을 취소하고, 뒤로 돌아간다.
3. 모든 빈 칸이 채워질 때까지 반복한다.

---

⭐️ 정답 코드 및 설명

#include<iostream>
#include<deque>

using namespace std;

int myMap[9][9];
int num[] = { 1,2,3,4,5,6,7,8,9 };
bool isComplete = false;
deque<pair<int, int>> toFill;

bool canFill(int X, int Y, int num) {

    // 3*3 격자 안에 같은 수가 있으면 못넣음
    int cy = (Y / 3) * 3, cx = (X / 3) * 3;
    for (int y = cy; y < cy + 3; y++) {
        for (int x = cx; x < cx + 3; x++) {
            if (myMap[y][x] == num) return false;
        }
    }

    for (int x = 0; x < 9; x++) {
        if (myMap[Y][x] == num) return false;
    }

    for (int y = 0; y < 9; y++) {
        if (myMap[y][X] == num) return false;
    }


    return true;
}

void dfs() {
    if (isComplete) return;

    while (!toFill.empty()) {
        int cy = toFill.front().first, cx = toFill.front().second; toFill.pop_front();
        for (int i = 0; i < 9; i++) {
            if (canFill(cx, cy, num[i])) {
                myMap[cy][cx] = num[i];
                dfs();
                if (isComplete) return;
                myMap[cy][cx] = 0;
            }
            if (i == 8) {
                toFill.push_front({ cy,cx });
                myMap[cy][cx] = 0;
                return;
            }
        }
    }
    isComplete = true;
    return;
}

void input() {
    for (int y = 0; y < 9; y++) {
        for (int x = 0; x < 9; x++) {
            cin >> myMap[y][x];
            if (myMap[y][x] == 0) toFill.push_back({ y,x });
        }
    }
}

int main() {

    input();
    dfs();
    for (int y = 0; y < 9; y++) {
        for (int x = 0; x < 9; x++) {
            cout << myMap[y][x] << " ";
        }
        cout << endl;
    }
    return 0;
}

---

🤔 문제 후기

처음에는 스도쿠 문제여서 스도쿠처럼 가로, 세로, 섹터를 나눠서 풀려고 했다. 이 방식의 문제점으로는 모든 칸에 여러 개의 숫자가 동시에 들어갈 수 있다면, 특정 숫자를 지정해서 할 수가 없다는 점이다. 그래서 DFS 방식을 사용하기로 했다. 물론 정상적으로는 9^81 이므로 시간 안에 해결할 수 없다. 하지만, 숫자가 채워질수록 가로, 세로, 섹터에 경우의 수가 줄어드는 것이므로 시간 안에 가능은 할 것이라 생각했다. 문제 자체가 골드 4 문제 치고도 어려운 문제였다고 생각한다.