[2239, 2580] 스도쿠

문제 출처 : https://www.acmicpc.net/problem/2580, https://www.acmicpc.net/problem/2239

분류 : 백트래킹

백준 2239, 2580 스도쿠

스도쿠의 답을 찾아라

---

구현 포인트

1) 백트래킹(DFS)

2) 2239번의 경우 사전식 우선순위를 고려하여 코딩해 주어야 한다. 

이 문제에 대해 글을 남기는 이유는 이 문제가 삼성 SDS에 초청되어 campus tour를 갔을 때

삼성 SW 역량평가 중에 어려운 문제의 수준과 유사하다고 했기 때문이다.

푸는데는 약 30분 정도가 소요되었다.

2239를 풀고 2580을 푸는데 문제가 완전 똑같아서 푼 문제 수만 1개 늘려주었다. 개이득!

스도쿠의 빈칸 좌표를 모두 저장한 후(vec), 하나씩 꺼내어 가능한 경우를 오름차순 순으로 선택하여 다음 좌표를 보는 방식으로

DFS를 실행하여 정답을 구했다.

하나가 완성되면 모든 함수를 종료하게끔 infinished 라는 bool형 flag를 통해 재귀호출된 함수를 모두 종료시켰다.

s_coord는 3 x 3 범위를 보기위해 각 좌표마다 저장한 좌표 배열이다.

예를 들어 (5, 6)이 스도쿠의 빈칸이라면 이 빈칸에 가능한 경우를 보기 위해서는 아래, 위와 (3,6)으로부터 3x3의 칸을 보아야 한다.

코드는 아래와 같다.

#include<cstdio>
#include<vector>
using namespace std;
 
bool isfinished = false;
vector< vector<int> > map(9, vector<int>(9, 0));
vector< pair<int, int> > vec;
vector< pair<int, int> > s_coord;
 
void dfs(int indx) {
    auto cur = vec[indx];
    int i = cur.first, j = cur.second;
    bool n[9] = { 1,1,1,1,1,1,1,1,1 };
    for (int k = 0; k < 9; k++) {
        int n1 = map[i][k] - 1, n2 = map[k][j] - 1;
        if (n1 != -1)
            n[n1] = false;
        if (n2 != -1)
            n[n2] = false;
    }
    auto start = s_coord[indx];
    for (int x = start.first; x < 3 + start.first; x++) {
        for (int y = start.second; y < 3 + start.second; y++) {
            int tmp = map[x][y] - 1;
            if (tmp != -1)
                n[tmp] = false;
        }
    }
    for (int k = 0; k < 9; k++) {
        if (n[k]) {
            map[i][j] = k + 1;
            if (indx + 1 == vec.size()) {
                isfinished = true;
                return;
            }
            else if (indx + 1 < vec.size()) {
                dfs(indx + 1);
                if (isfinished) return;
                map[i][j] = 0;
            }
        }
    }
}
 
int main() {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            scanf("%1d", &map[i][j]);
            if (!map[i][j]){
                vec.emplace_back(i, j);
                s_coord.emplace_back((i / 3) * 3, (j / 3) * 3);
            }
        }
    }
    dfs(0);
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            printf("%d ", map[i][j]);
        }
        printf("\n");
    }
}