[BOJ][C++] 백준 2239번: 스도쿠

https://www.acmicpc.net/problem/2239

2239번: 스도쿠

 

문제

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

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

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

입력

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

출력

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

제한

• 12095번 문제에 있는 소스로 풀 수 있는 입력만 주어진다.
  • C++17: 180ms
  • Java 15: 528ms
  • PyPy3: 2064ms

 

풀이

[🏕️ ICPC Sinchon Novice] - [BOJ][C++] 백준 2580번: 스도쿠

[BOJ][C++] 백준 2580번: 스도쿠

와 거의 동일한 문제..! 인데 이제 인풋을 연속된 수로 받기때문에 char 로 받아서 int 로 변환해서 연산하는 과정이 필요하다.

 

2580과 동일하게 풀었는데 틀렸다고 뜨는 경우 출력 형식을 자세히 보자 !!

최소가 되는 한가지 경우를 출력해야하기 때문에 빈 칸 중 앞 칸부터 적은 수부터 넣어가며 백트래킹을 해 나가야 한다.

나의 경우 빈 칸의 위치들을 벡터로 관리했으나 이중 for문으로 앞부터 뒤까지 차례대로 돌아도 상관 없다 (시간 복잡도..가 좀 커질뿐)

 

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> ci;

vector<vector<int>> board(9, vector<int>(9,0));
vector<ci> blank;  // 빈 칸의 좌표 정보들
int blankNum;
bool row[10][10]; // col[x][y] = x번째 열에 y라는 숫자가 있는가?
bool col[10][10];
bool box[10][10];
bool isFound = false;

void sudoku(int index) {
    if(index == blankNum) {
        for(int i=0; i<9; i++) {
            for(int j=0; j<9; j++)
                cout << board[i][j];
            cout << "\n";
        }
        isFound = true;
        return;
    }
    
    ci curPos = blank[index];
    int x = curPos.first;
    int y = curPos.second;
    for(int i=1; i<=9; i++) {
        if(row[x][i] || col[y][i] || box[(x/3)*3+(y/3)][i])
            continue;
        if(isFound)
            return;
        board[x][y] = i;
        row[x][i] = col[y][i] = box[(x/3)*3+(y/3)][i] = true;
        sudoku(index+1);
        row[x][i] = col[y][i] = box[(x/3)*3+(y/3)][i] = false;
    }
    
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    // 초기화
    for(int i=0; i<9; i++)
        for(int j=0; j<9; j++)
            box[i][j] = col[i][j] = box[i][j] = false;
          
    // 입력
    char ch; int input;
    for(int i=0; i<9; i++) {
        for(int j=0; j<9; j++) {
            cin >> ch;
            input = (int)ch - '0';
            if(input==0)
                blank.push_back({i,j});
            board[i][j] = input;
            row[i][input] = true;
            col[j][input] = true;
            box[(i/3)*3+(j/3)][input] = true;
        }
    }
    blankNum = blank.size();
    
    // 연산
    sudoku(0);
    
    
    return 0;
}

/*
 */