[백준] 9291번 : 스도쿠 채점 (C++)

9291번 : 스도쿠 채점

---

문제)

스도쿠는 일본어로 "수독(數獨)"을 읽은 것이다. 이는 미국에서 유명한 일본의 한 퍼즐 이름이기도 하다. 스도쿠는 9x9 격자판에 다음 조건을 만족하여 수를 채워 넣는 게임이다.

• 각 정수 1-9는 각 행에 정확히 한 번씩 등장해야 한다.
• 각 정수 1-9는 각 열에 정확히 한 번씩 등장해야 한다.
• 각 정수 1-9는 각 작은 3x3 정사각형에 정확히 한 번씩 등장해야 한다.

남규는 스도쿠에 푹 빠져서 하루종일 스도쿠 문제를 풀던 와중, 스도쿠를 풀었지만 그것이 정답인지를 쉽게 확인할 수 없어 고민에 빠졌다. 불쌍한 남규를 위해 다 채워진 스도쿠 판이 올바른 답인지 판별하는 프로그램을 작성해 주자.

 

 

 

입력 :

입력의 첫 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 9개의 줄로 이루어져 있으며, 각 줄에는 9개의 정수가 공백으로 구분되어 있다. 각 정수는 1 이상 9 이하이다. 테스트 케이스의 사이에는 빈 줄이 하나 있다.

테스트 케이스의 개수는 100개를 넘지 않는다.

 

 

 

출력 :

각 테스트 케이스에 걸쳐 "Case x:"를 출력한 후, 공백 한 칸 뒤에 풀이가 올바르면 "CORRECT"를, 아니면 "INCORRECT"를 출력한다. x는 테스트 케이스 번호이며, 1부터 시작한다.

 

 

 

 

 

풀이)

 

// 9291. 스도쿠 채점
#include <iostream>
#include <vector>
 
using namespace std;
 
int t;
 
bool check(vector<vector<int>>& vec)
{
    int visited[10] = { 0 };
    int cnt = 0;
    for (int i = 0; i < 9; i++)
    {
        if (!visited[vec[0][i]])
        {
            visited[vec[0][i]] = 1;
            cnt++;
        }
    }
 
    // 1 ~ 9까지가 없다면 false
    if (cnt != 9) return false;
 
    for (int i = 0; i < 9; i++)
    {
        fill(&visited[0], &visited[10], 0);
        cnt = 0;
        for (int j = 0; j < 9; j++)
        {
            if (!visited[vec[j][i]])
            {
                visited[vec[j][i]] = 1;
                cnt++;
            }
        }
 
        if (cnt != 9) return false;
    }
 
 
    // 각 영역의 첫 포인트를 지정해 주는 i와 j
    //    1 2 3 
    //    4 5 6
    //  7 8 9
 
    for (int i = 0; i < 9; i += 3)
    {
        for (int j = 0; j < 9; j += 3)
        {
            int x = i;
            int y = j;
 
            fill(&visited[0], &visited[10], 0);
            cnt = 0;
 
            // 해당 i, j 포인트로부터 3x3 배열을 확인한다.
            for (int k = x; k < x + 3; k++)
            {
                for (int l = y; l < y + 3; l++)
                {
                    if (!visited[vec[k][l]])
                    {
                        visited[vec[k][l]] = 1;
                        cnt++;
                    }
                }
            }
 
            if (cnt != 9) return false;
        }
    }
 
    return true;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> t;
    
    for(int i = 1; i < t + 1 ;i++)
    {
        vector<vector<int>>vec;
        vec.resize(9, vector<int>(9, 0));
        for (auto& ele : vec) for (auto& e : ele) cin >> e;
        
        cout << "Case " << i << ": ";
 
        if (check(vec))
        {
            cout << "CORRECT\n";
        }
        else
        {
            cout << "INCORRECT\n";
        }
    }
    
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/9291 

9291번: 스도쿠 채점