2580번 스도쿠

한국정보올림피아드 초등부 문제이다.

나에게 제일 어려운 BackTracking 문제이다.

역시나 어려워서 다른 블로거 분 코드를 많이 참고하였다. 뭔가 계속 참고하는 것이 죄송스럽다.

(언젠가는 나도 새로운 문제에 대해서 풀 수 있겠지..?)

이 문제 풀면서 기억해야할 것

1. 배열을 선언할 때 조심하자. 

처음에 [9][9]로 선언했었다가, 답이 안 나와서 생각해보니 코드 70번 째 줄에 i의 범위 때문이었다.

2. print() 함수는 120번 째 줄 이후에 선언하면 안 된다.

왜냐하면, 81 ~ 84번 째 코드들로 인해 sudoku 배열이 다시 원래대로 되돌아 가기 때문이다.

3. vector을 배열 index로 활용하는 Skill을 기억하자.

이 문제와 15683번 감시(http://hsdevelopment.tistory.com/8) 등등

4. square 영역 설정하는 방법을 기억하자.

squareBool 함수

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

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int sudoku[10][10] = { 0, };
 
bool row[10][10] = { false, }; // row[그 행에][해당 숫자가 있는지 여부]
bool column[10][10] = { false, }; // column[그 열에][해당 숫자가 있는지 여부]
bool square[10][10] = { false, }; // square[그 영역에][해당 숫자가 있는지 여부]
 
bool stop = false;
 
vector<pair<int, int> > zero;
 
/*
square
0 1 2
3 4 5
6 7 8
*/
 
void squareBool(int r, int c, int area)
{
    for (int i = r; i < r + 3; i++)
    {
        for (int j = c; j < c + 3; j++)
        {
            square[area][sudoku[i][j]] = true;
        }
    }
}
 
void print()
{
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            printf("%d ", sudoku[i][j]);
        }
 
        printf("\n");
    }
}
 
void BackTracking(int index)
{
    if (stop) return;
 
    if (index == zero.size())
    {
        stop = true;
 
        print();
 
        return;
    }
 
    int y = zero[index].first;
    int x = zero[index].second;
    int area = 3 * ( y / 3 )  + x / 3;
 
    for (int i = 1; i <= 9; i++) // 스도쿠 숫자 1 ~ 9
    {
        if (!row[y][i] && !column[x][i] && !square[area][i])
        {
            row[y][i] = true;
            column[x][i] = true;
            square[area][i] = true;
            sudoku[y][x] = i;
 
            BackTracking(index + 1); // 백트래킹
 
            row[y][i] = false;
            column[x][i] = false;
            square[area][i] = false;
            sudoku[y][x] = 0;
        }
    }
}
 
int main(void)
{
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            scanf("%d", &sudoku[i][j]);
 
            row[i][sudoku[i][j]] = true;
            column[j][sudoku[i][j]] = true;
 
            if (sudoku[i][j] == 0)
            {
                zero.push_back({ i, j });
            }
        }
    }
 
    int area = 0;
 
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            squareBool(i * 3, j * 3, area);
 
            ++area;
        }
    }
 
    BackTracking(0);
 
    return 0;
}