[C++][백준 2239] 스도쿠

문제설명은 더보기를 눌러주세요

문제링크 : www.acmicpc.net/problem/2239

문제

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

입력

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

출력

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

 

-풀이-

백트래킹을 이용하는 문제

1. 입력받을 때 0인 공간을 벡터에 저장

2. 벡터를 돌며, 현재 칸에 1~9까지의 수 중 들어갈 수 있는 수가 있다면 넣어주고 다음 칸으로

3. 현재 칸에 들어갈 수 있는 칸이 없다면 return 되고, 2.번에서 반복문에 의해 다른 수를 넣어줄 것

4. 모든 칸에 숫자가 처음으로 입력되면 그게 정답 (1부터 순차적으로 넣었기 때문)

-코드-

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
bool isCorrect(int x, int y, int k);
void DFS(int idx);
void printMap();
int map[10][10];
int ans = 0;
vector<pair<int, int> > v;
int main(){
    string str;
    for(int i=1; i<=9; i++){
        cin >> str;
        for(int j=0; j<9; j++){
            map[i][j+1] = str[j] - '0';
            if(map[i][j+1] == 0) v.push_back(make_pair(i, j+1));
        }
    }   
    DFS(0); // 벡터의 0번째 index 부터 확인
    return 0;
}

void DFS(int idx){ 
    if(idx == v.size()) {
        printMap();
        exit(0);
    }
    int x = v[idx].first, y = v[idx].second;
    for(int j=1; j<=9; j++){
        if(isCorrect(x, y, j)) { // 가로, 세로, 3x3 모두 없는 수일 경우
            map[x][y] = j; // 해당 칸에 넣어주기
            DFS(idx+1); // 다음 depth로 
            map[x][y] = 0; // 백트래킹
        } 
    }
    return;
} 

bool isCorrect(int x, int y, int k){ 
    for(int i=1; i<=9; i++) { // 세로 중복 확인
        if(i == x) continue;
        if(map[i][y] == k) return false;
    }
    for(int i=1; i<=9; i++) { // 가로 중복 확인
        if(i == y) continue;
        if(map[x][i] == k) return false;
    }
    int tx, ty; // 3×3 크기의 보드에 중복 없는지 확인
    if(x%3 == 0) tx = x/3;
    else tx = x/3+1;
    if(y%3 == 0) ty = y/3;
    else ty = y/3+1;
    tx *= 3, ty *= 3;
    for(int i=tx-2; i<=tx; i++){
        for(int j=ty-2; j<=ty; j++){
            if(i == x && j == y) continue;
            if(map[i][j] == k) return false;
        }
    }
    return true;
}



void printMap(){
    for(int i=1; i<=9; i++){
        for(int j=1; j<=9; j++){
            cout << map[i][j];
        }
        cout << endl;
    }
}