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

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

2580번: 스도쿠

 

 

 

 

---

- 문제

 

  스도쿠가 주어지면 빈칸에 들어갈 숫자를 맞추는 문제다.

 

 

---

- 해설

 

혼자서 풀다가 잘 안되어서 내가 자주 참고하는 cryptosalamander라는 블로그의 내용을 참고해봤다. 역시 언제나 그렇듯 코드가 되게 깔끔하게 잘 짜여져 있었다.

 

나는 스도쿠 판을 9*9 모든 경우를 돌면서 문제를 해결하려고 해서 시간초과가 났지만,

 

이 분은 비어있는 0인 경우의 좌표를 기억해놔서 해당 경우만 정답을 찾게 해서 시간초과를 극복했다. 

 

내꺼랑 다른 점은, 위의 한 가지랑 내껀 반복문 안에서 모든 걸 해결하려해서 4중 반복문이 되었다는 것이 다른점 같다. 이렇게 필요에 따라 나눠 놓으니 가독성도 훨씬 좋고 이해가 잘 되니, 이렇게 하는 게 좋을 것 같다.

 

 

 

 

---

- 풀이

#include <iostream>
#include <vector>
using namespace std;

// cryptosalamander 티스토리꺼 참고해서 품

int board[9][9];
vector<pair<int, int>> points; // 여기에 0인 경우를 모두 저장해놔서 이것만 확인함, 내가 만들었던거는 9 * 9 모두 확인하면서 지나가서 시간초과
int cnt = 0;                   // 0의 개수 파악
bool found = false;

bool check(pair<int, int> p)
{
    int s_x = p.first / 3;
    int s_y = p.second / 3;
    for (int i = 0; i < 9; i++)
    {
        if (board[p.first][i] == board[p.first][p.second] && i != p.second)
        {
            return false;
        }
        if (board[i][p.second] == board[p.first][p.second] && i != p.first)
        {
            return false;
        }
    }
    for (int i = 3 * s_x; i < 3 * s_x + 3; i++)
    {
        for (int j = 3 * s_y; j < 3 * s_y + 3; j++)
        {
            if (board[i][j] == board[p.first][p.second]) // 이거 3으로 나눴다가 다시 3으로 곱하는거 중요!!!!!
            {
                if (i != p.first && j != p.second)
                {
                    return false;
                }
            }
        }
    }
    return true;
}

void sudoku(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';
        }
        found = true;
        return;
    }
    for (int i = 1; i <= 9; i++)
    {
        board[points[N].first][points[N].second] = i;
        if (check(points[N]))
        {
            sudoku(N + 1);
        }
        if (found)
        {
            return;
        }
    }
    board[points[N].first][points[N].second] = 0;
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    pair<int, int> point;
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            cin >> board[i][j];
            if (board[i][j] == 0)
            {
                cnt++;
                point.first = i;
                point.second = j;
                points.push_back(point);
            }
        }
    }
    sudoku(0);

    return 0;
}

 

 

---

- 새롭게 알게 된 점