Game Develop

[Algorithm] Baekjoon 2580번 : 스도쿠 본문

Algorithm/Baekjoon

[Algorithm] Baekjoon 2580번 : 스도쿠

MaxLevel 2022. 10. 13. 19:38

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

 

2580번: 스도쿠

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루

www.acmicpc.net

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
 
using namespace std;
 
 
 
vector<vector<int>> m(9, vector<int>(9));
vector<pair<int, int>> zeroMap;
int targetCount = 0;
bool isCheck = false;
 
 
 
bool check(int checkNum, int row, int col)
{
    // 행 검사
 
    for (int i = 0; i < 9; i++) // 2,5에 있다고 가정해보자..
    {
        if (i == col) continue; // 자기자신은 건너뛰기
        if (m[row][i] == checkNum) return false; // 같은수가 있으니 return false;
    }
 
    // 열 검사
    for (int i = 0; i < 9; i++)
    {
        if (i == row) continue;
        if (m[i][col] == checkNum) return false;
    }
 
    // 3 * 3 영역 검사.
 
    int startY = 3 * (row / 3);
    int startX = 3 * (col / 3);
 
    for (int i = startY; i < startY + 3; i++)
    {
        for (int j = startX; j < startX + 3; j++)
        {
            if (i == row && j == col) continue;
            if (m[i][j] == checkNum) return false;
        }
    }
 
    return true;
}
 
void solution(int index)
{
    if (index == zeroMap.size())
    {
        isCheck = true;
        return;
    }
 
    for (int i = 1; i <= 9; i++)
    {
        if (check(i, zeroMap[index].first, zeroMap[index].second))
        {
            m[zeroMap[index].first][zeroMap[index].second] = i;
            solution(index + 1);
        }
        if (isCheck) return;
    }
 
 
    m[zeroMap[index].first][zeroMap[index].second] = 0; // 정답루트가 아니면 다시 되돌리기.
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int temp = 0;
    int zeroCount = 0;
 
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            cin >> temp;
            m[i][j] = temp;
 
            if (temp == 0)
            {
                zeroCount++;
                zeroMap.push_back({ i,j });
            }
        }
    }
 
    targetCount = zeroCount;
 
    solution(0);
 
    cout << endl << endl;
 
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            cout << m[i][j] << ' ';
        }
        cout << endl;
    }
}
 
 
 
 cs

 

처음 0 위치부터 시작해서 DFS를 돌리면 된다. 계속 타고 내려가다가 targetCount만큼 되어야만 모든 탐색을 종료시킨다.

'Algorithm > Baekjoon' 카테고리의 다른 글

[Algorithm] Baekjoon 10597번 : 순열장난  (0) 2022.10.13
[Algorithm] Baekjoon 2661번 : 좋은수열  (1) 2022.10.13
[Algorithm] Baekjoon 1405번 : 미친 로봇  (0) 2022.10.13
[Algorithm] Baekjoon 1339번 : 단어 수학  (0) 2022.10.13
[Algorithm] Baekjoon 2589번 : 보물섬  (1) 2022.10.08
'Algorithm/Baekjoon' Related Articles more