[백준] 2580 - 스도쿠 (C++)

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

스도쿠는 가로, 세로 각각 9개씩 총 81개의 칸으로 이루어진 정사각형 판에서 이루어지는 게임으로, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈칸을 채우는 방식은 다음과 같다.

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
2. 굵은 선으로 구분된 3×3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈칸이 채워진 최종 모습을 출력하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 12095번 문제에 있는 소스로 풀 수 있는 입력만 주어진다.
• C++14: 80ms
• Java: 292ms
• PyPy3: 1172ms
• 스도쿠 판을 채우는 방법이 여럿인 경우엔 그중 하나만 출력한다.

 

스도쿠 판의 모든 빈칸에 1부터 9까지 모든 수를 넣어보고 유망한지 아닌지 판단해야 한다. 유망한 경우에만 다음 빈칸으로 넘어가고 반복문을 계속해서 진행한다.

 

스도쿠 판을 채운 뒤 하나만 출력하고 프로그램을 종료시켜야 하기 때문에 처음엔 bool 변수를 통해 한 번 출력했다면 true로 바꿔 다음부턴 종료 조건을 만나더라도 스도쿠 판을 출력하지 않게 설계했는데, 그렇게 구현하면 스도쿠 판이 모두 빈칸일 때 프로그램이 종료되질 않았다. 해결하려면 return;으로 함수를 종료시키는 것보단, exit(0);을 통해 프로세스(스레드)를 종료시키도록 구현해야 한다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. 스도쿠 판 입력받고 빈칸은 vector에 따로 기록하기
2. void dfs(int depth) 함수로 백트래킹 진행
   
   1. 종료 조건은 depth가 빈칸을 기록해 둔 zeros vector 크기와 동일할 때, 완성된 스도쿠 판을 출력하고 exit(0);을 통해 프로그램을 종료
   2. zeros vector의 depth번째 좌표에 대해 스도쿠 판에 반복문으로 1~9까지의 숫자를 넣었을 때 조건을 만족한다면 dfs(depth+1);을 통해 백트래킹 진행, 이후 스도쿠 판에 넣은 값을 0으로 초기화
      1. 조건 만족 → 행, 열, 3×3 그리드 안에 스도쿠 판에 넣은 숫자와 겹치는 숫자가 있는지 확인 (없어야 만족)

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해 보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

1회차

• proper() 함수에서 grid 조건을 만족하는지 확인할 때 if문의 조건을 잘못 설정함
• 백트래킹 함수를 진행하고 난 뒤 0으로 초기화하도록 수정
• 백트래킹 종료 조건에서 스도쿠 판을 출력하는 조건(bool 값)을 없애고 무조건 출력하게 한 뒤 exit(0);을 통해 프로그램을 종료시키도록 함

 

---

정답 코드

#include <iostream>
#include <vector>
#define pii pair<int,int>
using namespace std;

int board[9][9];
vector<pii> zeros;
bool found;

void printb() {
    for (int i=0; i<9; i++) {
        for (int j=0; j<9; j++) cout << board[i][j] << ' ';
        cout << '\n';
    }
}

bool proper(int x, int y, int num) {
    // row
    for (int i=0; i<9; i++) {
        if (i!=y && board[x][i]==num) return false;
    }

    // col
    for (int i=0; i<9; i++) {
        if (i!=x && board[i][y]==num) return false;
    }

    // grid
    for (int i=0; i<3; i++) {
        for (int j=0; j<3; j++) {
            int cx=x/3*3+i, cy=y/3*3+j;
            if ((cx!=x || cy!=y) && board[cx][cy]==num) return false;
        }
    }

    return true;
}

void dfs(int dep) {
    if (dep==zeros.size()) {
        printb();
        exit(0);
        return;
    }
    auto [a,b] = zeros[dep];
    for (int i=1; i<=9; i++) {
        board[a][b] = i;
        if (proper(a,b,i)) dfs(dep+1);
        board[a][b] = 0;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    for (int i=0; i<9; i++) {
        for (int j=0; j<9; j++) {
            cin >> board[i][j];
            if (board[i][j]==0) zeros.push_back({i,j});
        }
    }
    
    dfs(0);
}