반응형
문제링크:https://www.acmicpc.net/problem/2580
2580번: 스도쿠
스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루
www.acmicpc.net
일반적인 방법으로 풀면은 시간초과입니다.
dfs를 사용하고 이미 확인한 값에 대해서는 탐색하지 않는 백트래킹 기법을 사용해야 하는 어려운 문제였습니다.
이문제에서의 핵심은
bool row[9][10] = { 0 };
bool col[9][10] = { 0 };
bool square[9][10] = { 0 };
세가지 방문여부입니다. row는 해당 행에서 수를 탐색했는지 여부, col은 열에서 수를 탐색했는지 여부, square는 속하는 3x3에서 수를 탐색했는지 여부를 판단합니다.
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++) {
cin >> arr[i][j];
if (arr[i][j] != 0)
{
row[i][arr[i][j]] = true;
col[j][arr[i][j]] = true;
square[(i / 3) * 3 + (j / 3)][arr[i][j]] = true;
}
}
dfs(0);
}위 처럼 수를 입력받으면 row, col, square에 방문 수를 저장합니다.
row[i][j] 라면 i행에서 j값을 방문했는지 여부를 표시합니다 즉 row[1][9]= true 면은 1행에 9는 존재한다는 의미입니다.
col과 square 모두 같은 맥락입니다.
이때 스퀘어는
위와 같은 구조로 진행됩니다. (출처: 얍문님 티스토리)
그렇기 때문에 (y/3)*3 + x/3 을 통해서 해당 위치에 표시하는 것입니다.
정답코드입니다. cnt값을 올려주며 진행하게 됩니다. 81일때에는 모든 값들이 채워져 있는 것이기에 종료하게 됩니다.
이때 exit(0)를 이용해서 바로 프로세스를 종료해버리면 시간을 단축시킵니다. 천천히 이해해보세요.
#include <iostream>
#include <cstring>
#include <stdlib.h>
using namespace std;
int arr[9][9] = { 0 };
bool row[9][10] = { 0 };
bool col[9][10] = { 0 };
bool square[9][10] = { 0 };
void dfs(int cnt) {
if (cnt == 81) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++)
cout << arr[i][j] << ' ';
cout << endl;
}
exit(0);
}
int y = cnt / 9;
int x = cnt % 9;
if (arr[y][x] != 0)
dfs(cnt + 1);
else {
for (int i = 1; i <= 9; i++) {
if (row[y][i] == 0 && col[x][i] == 0 && square[(y / 3) * 3 + (x / 3)][i] == 0) {
row[y][i] = 1;
col[x][i] = 1;
square[(y / 3) * 3 + (x / 3)][i] = 1;
arr[y][x] = i;
dfs(cnt + 1);
arr[y][x] = 0;
row[y][i] = 0;
col[x][i] = 0;
square[(y / 3) * 3 + (x / 3)][i] = 0;
}
}
}
return;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++) {
cin >> arr[i][j];
if (arr[i][j] != 0)
{
row[i][arr[i][j]] = true;
col[j][arr[i][j]] = true;
square[(i / 3) * 3 + (j / 3)][arr[i][j]] = true;
}
}
dfs(0);
}
반응형
'알고리즘 > DFS' 카테고리의 다른 글
| [백준] 2023-신기한 소수(C++) (0) | 2021.01.02 |
|---|---|
| [백준] 14267-내리 칭찬(C++) (0) | 2021.01.01 |
| [백준] 9663-N-Queen(C++) (0) | 2020.07.27 |
| [백준] 2573-빙산(C++) (0) | 2020.06.09 |
| [백준] 1987-알파벳(C++) (0) | 2020.06.09 |