https://www.acmicpc.net/problem/2580
2580번: 스도쿠
스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루
www.acmicpc.net
DFS 백트래킹 활용 문제
1. DFS 백트래킹을 사용하여 1~9까지의 숫자 넣기
2. 입력되는 (1~9) 숫자가 조건에 맞는지 확인
2-1. 같은 행 안에 중복으로 존재하지 않는지
2-2 같은 열 안에 중복으로 존재하지 않는지
2-3 3x3 배열 안에 중복으로 존재하지 않는지
즉, 백트래킹 방식으로 돌면서 2번의 조건을 모두 만족하는 경우에만 0의 위치를 그 값으로 변환한다.
그 다음 맵에 있는 0의 숫자만큼 모두 변경 되었다면 스도쿠를 출력해주면 끝
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int map[10][10],cnt;
vector<pair<int, int> > vec;
bool check ( int x, int y, int num ){
for(int i=0; i<9; i++){
if(map[x][i]==num){
return false;
}
}
for(int i=0; i<9; i++){
if(map[i][y]==num){
return false;
}
}
x = x/3;
y = y/3;
for(int i= x*3; i<x*3+3; i++){
for(int j= y*3; j<y*3+3; j++){
if(map[i][j] == num) {
return false;
}
}
}
return true;
}
void DFS(int L ){
if(L== cnt){
for(int i=0; i<9; i++){
for(int j=0; j<9; j++){
cout<<map[i][j]<<" ";
}
cout<<"\n";
}
exit(0);
}
else{
for(int i=1; i<=9; i++){
int x = vec[L].first;
int y = vec[L].second;
if(check(x,y,i)){
map[x][y] = i;
DFS(L+1);
map[x][y] = 0;
}
}
}
}
int main(){
for(int i=0; i<9 ; i++){
for(int j=0; j<9; j++){
cin>>map[i][j];
if(map[i][j] == 0){
vec.push_back(make_pair(i,j));
cnt++;
}
}
}
DFS(0);
}'Algorithm > BOJ' 카테고리의 다른 글
| [c++] 백준 2210 숫자판 점프 (0) | 2021.07.17 |
|---|---|
| [c++] 백준 14889 스타트와 링크 (0) | 2021.07.15 |
| [c++] 백준 14923 미로 탈출 (0) | 2021.07.12 |
| [c++] 백준 14502 연구소 (0) | 2021.07.12 |
| [c++] 백준 1987 알파벳 (0) | 2021.07.11 |