[BOJ/C++] 2580: 스도쿠

🏅 Gold 4

✏️ 1차 솔루션

1. 0이면 해당 좌표 queue 에 넣기
2. 0인 좌표를 포함하는 가로, 세로, 3*3 board 각각의 0이 아닌 숫자 표시하는 bool 배열
3. 0인 좌표의 가로에 없는 숫자를 queue 에 넣어서 0인 좌표가 될 수 있는 숫자 저장
4. 3번의 queue 에 저장된 좌표가 될 수 있는 숫자가 세로, 9개 set에도 없으면서 현재 좌표가 0일 경우 좌표에 해당 숫자 넣기 ➡️ 이미 채웠는데 덮어씌우는 것 방지

🚨 1차 trouble

왠지 틀렸다고 뜬다ㅠ
for 문도 빈번하게 사용하고 배열이나 큐도 너무 많이 사용해서 그런 것 같다ㅠ

✏️ 최종 솔루션

• sol(int n) 함수
  ➡️ 빈 칸에 숫자를 채우고 빈 칸을 다 채웠을 경우, 결과 출력
  ➡️ n: 빈 칸을 채운 횟수를 표기하면서 현재 채울 빈 칸의 좌표 인덱스를 의미, 빈 칸 채울 때마다 n 값 늘려서 재귀
• check(edge e) 함수
  ➡️ 현재 좌표의 board 값은 새로 채운 값인데 같은 값이 가로, 세로, 3*3 내에 존재하는지 확인하고 존재하면 false return

1. 빈 칸의 좌표는 vector 에 따로 저장하고 빈 칸의 개수도 cnt 에 저장
2. 현재 빈칸의 좌표에 1부터 9까지 넣어보기
   1) check(현재좌표) 의 return 값이 true 이면 이대로 채워넣어도 괜찮다는 의미이기 때문에 n 값 늘려서 재귀
3. n 값이 cnt 값과 동일하면 현재 스도쿠 출력하고 bool 변수로 스도쿠 완성 여부 표기
4. 스도쿠 완성되었다면 return 해서 바로 종료하기

📌 self feedback

가로, 세로, 3*3 에 같은 숫자가 있는지 확인하기 위해 배열을 남발하지 말고 현재 위치에서 같은 숫자가 있는지의 여부를 함수를 통해 확인할 수 있도록 계획했어야 했음
for 문의 사용을 자제하느라 빈 칸에 들어갈 수 있는 수가 아니면 아예 넣을 수 없도록 하는 방향으로 풀이했는데 가능한 숫자의 범위가 제한적이기 때문에 무지성으로 1~9 까지 넣고 가능한지 여부를 판단하는 풀이가 더 적합

✏️ 최종 code

#include <iostream>
#include <vector>

using namespace std;

struct edge {
    int x;
    int y;
};

int board[9][9];
int cnt=0;
vector<edge> blank;
bool comp=false;    // 스도쿠 완성 여부

// 같은 숫자 있는지 검사 -> 스도쿠 성립가능한지 판단
bool check(edge e) {
    int x=e.x;
    int y=e.y;
    
    // 가로, 세로에 같은 숫자 있는지 확인
    for (int i=0; i<9; i++) {
        if (board[x][i]==board[x][y] && i!=y) return false;
        if (board[i][y]==board[x][y] && i!=x) return false;
    }
    
    // 3by3에 같은 숫자 있는지 확인
    int nx=x/3*3;
    int ny=y/3*3;
    for (int i=nx; i<nx+3; i++) {
        for (int j=ny; j<ny+3; j++) {
            if (board[i][j]==board[x][y] && i!=x && j!=y) return false;
        }
    }
    
    return true;
}

void sol(int n) {
    // 빈칸 다 채웠을 경우, 결과 출력
    if (n==cnt) {
        for(int i=0;i<9;i++) {
            for(int j=0;j<9;j++) {
                cout << board[i][j] << " ";
            }
            cout << '\n';
        }
        comp=true;  // 스도쿠 완성하면 return했을 때 더 갱신하지 않기위해 표시
        return;
    }
    
    // 빈 칸에 1부터 9 까지 넣어봄
    for (int i=1; i<=9; i++) {
        board[blank[n].x][blank[n].y]=i;
        // true 이면 중복되는 숫자가 없다는 의미이므로 이대로 채워넣어도 ㄱㅊ -> 다음 빈칸 채우러 가기
        if (check(blank[n])) sol(n+1); // 한 칸 채웠기 때문에 n 늘려주기
        if(comp) return;    // 스도쿠 완성되면 종료
    }
    
    // 최적 값 못 찾으면 값 비우기
    board[blank[n].x][blank[n].y]=0;
    return;
}

int main() {
    ios_base::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) {
                blank.push_back({i,j});
                cnt++;
            }
        }
    }
    
    sol(0);
    
}