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

 

 

문제 

2580번: 스도쿠

 

🔎문제 해석

해당 칸에서 숫자를 넣고, 가로줄, 세로줄, 3*3 사각형 범위 검사를 해서 통과하면 다음 단계를 진행하는 문제이다.
만약 막혔다면 이전단계에서 다른 숫자를 선택하는 백트래킹 알고리즘을 사용하면 된다.

 

해당 좌표에서 포함되는 사각형의 범위는 어떻게 구하면 될까?

만약 x, y 좌표가 0,0이라면 사각형은 첫 번째 범위일 것이다.

가로 범위에서 3개의 구분이 있고, 세로 범위에서 3개의 구분이 있다.

따라서 (x좌표 /3 , y좌표/3)이 해당 사각형의 범위일 것이다.

만약 (5,5)라면 (5/3,5/3)= (1,1)에 해당하는 사각형의 범위일 것이다.

 

가로줄 검사와 세로줄 검사는 해당 x, y좌표를 고정시켜 놓고, 끝까지 탐색하면 된다.

 

💡즉 알고리즘 방향은 이러하다.

1.  pair 형태로 빈칸들을 저장해 놨다.
2. pair의 원소들을 한 칸씩 탐색한다.
3. 해당 원소의 x, y좌표에 숫자를 1~9까지 넣어서 탐색을 시작(재귀 함수)한다.
   1. 탐색은 가로줄, 세로줄, 사각형의 범위를 검사한다.
      1. 검사를 하는데 만약 실패한다면 x, y좌표에 그다음 숫자를 넣고 3번 과정을 시작.
      2. 성공한다면 4번 과정 진행
4. 해당 x,y좌표에 숫자를 방문처리 해주고, 그 다음 pair의 원소를 탐색함(3번 과정)
5. 만약 그다음 원소에서 1~9까지 넣어도 검사를 통과하지 못한다면 그 이전의 탐색으로 돌아가서 새로운 숫자로 탐색을 시작함.
6. 탐색을 하다가 만약 pair의 마지막원소까지 도달한다면 그때 배열을 출력하고, 종료한다.
   1. 단 하나의 배열만 출력하라고 했기에, 종료해야 한다. 종료하지 않는다면 여러 개의 배열이 출력될 가능성이 있다.

 

💻전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int> > graph;
vector<pair<int, int> > blank;
void funct(int idx);
bool check(int row, int col, int num);
bool square(int ropt, int copt, int num);
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    graph.resize(9, vector<int>(9, 0));
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            cin >> graph[i][j];
            if (graph[i][j] == 0)
            {
                blank.push_back(make_pair(i, j));
            }
        }
    }
    funct(0);
}
void funct(int idx)
{
    if (idx == blank.size()) //만약 모든 빈칸을 채웠다면 그때 출력하고 종료.
    {
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                cout << graph[i][j] << " ";
            }
            cout << "\n";
        }
        exit(0);
    }
    else
    {
        auto loc = blank[idx];
        for (int i = 1; i <= 9; i++)
        {
            if (check(loc.first, loc.second, i) == true)
            {
                // 적절한 좌표.
                graph[loc.first][loc.second] = i;
                funct(idx + 1); // 다음거.
                graph[loc.first][loc.second] = 0;
            }
        }
    }
}
bool check(int row, int col, int num)
{
    for (int i = 0; i < 9; i++)
    {
        if (num == graph[row][i])
            return false;
        if (num == graph[i][col])
            return false;
    }
    // 3*3사각형
    int ropt = row / 3, copt = col / 3;
    if (!square(ropt, copt, num))
    {
        return false;
    }
    return true;
}
bool square(int ropt, int copt, int num)
{
    int startCol = copt * 3;
    int startRow = ropt * 3;
    for (int i = startRow; i < startRow + 3; i++) //3*3 사각형 검사
    {
        for (int j = startCol; j < startCol + 3; j++)
        {
            if (graph[i][j] == num)
                return false;
        }
    }
    return true;
}

주석을 달아놨으니, 주석을 봐주십셔🙏

 

😃느낀 점

• 재귀함수를 진행할 때 처음에 ++idx로 했는데, 이게 idx+1과 다른 의미라는 걸 망각한 채, 코드를 짜서 한참 헤맸다.
  • 알고리즘은 분명히 맞는데, 재귀 부분에서 계속 오류가 생겼는데, 이런 오류일 줄은 몰랐다..
• 전형적인 백트래킹 알고리즘이다!