[백준/Baekjoon] 2580 스도쿠 C++ :: Back tracking & Implementation

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

2580번: 스도쿠

---

1. Logic

대표적인 백트래킹 문제.

 

문제를 푸는 로직은 아래와 같다.

1. 입력을 받으면서 0의 갯수(채워야 하는 빈칸의 갯수)를 같이 카운트한다.

2. solve함수의 파라미터로 0을 넣고 스도쿠 칸이 총 81칸이기 때문에 나누기, 나머지 연산자로 y, x칸의 좌표를 구한다. 나눗셈 연산 : y, 나머지 연산 x

3. 가로, 세로, 3*3에 이미 나온 숫자들이 있는지 확인하고 1~9까지 돌면서 안나온 숫자들중에서 가능한 숫자를 확인한다.

4. 숫자를 맞춰나가면서 처음에 센 0의 갯수와 채워 넣은 숫자의 갯수가 같아지면 바로 출력하고 리턴한다.

---

2. Code

#include <bits/stdc++.h>

using namespace std;

int sudoku[10][10];
bool numberVis[10];
int zero, solveCnt;

void init(int y, int x) {
    int startX = x - x%3;
    int startY = y - y%3;
    
    for(int i = 0; i < 10; i++) numberVis[i] = false;
    for(int i = 0; i < 9; i++) {
        numberVis[sudoku[i][x]] = true;
        numberVis[sudoku[y][i]] = true;
    }
    for(int i = startY; i < startY + 3; i++) {
        for(int j = startX; j < startX + 3; j++) {
            numberVis[sudoku[i][j]] = true;
        }
    }
}

bool availableNumCheck(int y, int x, int k) {
    int startX = x - x%3;
    int startY = y - y%3;
    
    //세로 확인
    for(int i = 0; i < 9; i++) {
        if(sudoku[i][x] == k) return false;
    }
    //가로확인
    for(int i = 0; i < 9; i++) {
        if(sudoku[y][i] == k) return false;
    }
    //3*3 확인
    for(int i = startY; i < startY + 3; i++) {
        for(int j = startX; j < startX + 3; j++) {
            if(sudoku[i][j] == k) return false;
        }
    }
    return true;
}

bool solve(int n) {
    if(solveCnt == zero) {
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                cout << sudoku[i][j] << ' ';
            }
            cout << "\n";
        }
        return true;
    }
    
    int i = n / 9;
    int j = n % 9;
    
    if(sudoku[i][j] == 0) {
        for(int k = 1; k <= 9; k++) {
            init(i, j);
            
            if(!numberVis[k] && availableNumCheck(i, j, k)) {
                sudoku[i][j] = k;
                numberVis[k] = true;
                solveCnt++;
                if(solve(n+1)) return true;
                sudoku[i][j] = 0;
                numberVis[k] = false;
                solveCnt--;
            }
        }
    }
    else return solve(n+1);
    
    return false;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    for(int i = 0; i < 9; i++) {
        for(int j = 0; j < 9; j++) {
            cin >> sudoku[i][j];
            if(sudoku[i][j] == 0) zero++;
        }
    }
    
    solve(0);
}

---

3. Feedback

아래 벨로그의 링크를 참고해서 풀었다. 숫자를 나눠서 나머지와 몫으로 구분한 아이디어가 너무 좋았다. 이분 블로그에 OS도 설명이 잘 되어있어 또한 참고할 것이다!! 정보+1.

https://velog.io/@junttang/BOJ-2580-%EC%8A%A4%EB%8F%84%EC%BF%A0-%ED%95%B4%EA%B2%B0-%EC%A0%84%EB%9E%B5

BOJ - 2580 스도쿠 해결 전략 (C++)

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐