백준 2580번 : 스도쿠
- 분류: 백트래킹
코드
#include <iostream>
#include <vector>
using namespace std;
int table[9][9];
bool flag = false;
vector<int> find_candidate(int i, int j) {
bool nums[9] = {false,};
for(int x=0 ; x<9 ; x++) {
if(table[x][j]!=0) nums[table[x][j]-1]=true;
}
for(int x=0 ; x<9 ; x++) {
if(table[i][x]!=0) nums[table[i][x]-1]=true;
}
for(int x=3*(i/3) ; x<3*(i/3)+3 ; x++) {
for(int y=3*(j/3) ; y<3*(j/3)+3 ; y++) {
if(table[x][y]!=0) nums[table[x][y]-1]=true;
}
}
vector<int> result;
result.clear();
for(int x=0 ; x<9 ; x++) if(!nums[x]) result.push_back(x+1);
return result;
}
void backtrack() {
for(int i=0 ; i<9 ; i++) {
for(int j=0 ; j<9 ; j++) {
if(table[i][j]==0) {
vector<int> candidates = find_candidate(i, j);
for(int c : candidates) {
table[i][j] = c;
backtrack();
if(flag) return;
}
table[i][j]=0;
return;
}
}
}
flag = true;
}
int main() {
for(int i=0 ; i<9 ; i++) {
for(int j=0 ; j<9 ; j++) {
cin >> table[i][j];
}
}
backtrack();
for(int i=0 ; i<9 ; i++) {
for(int j=0 ; j<8 ; j++) {
cout << table[i][j] << ' ';
}
cout << table[i][8] << '\n';
}
}
-
코멘트
백트래킹으로 풀 수 있는 전형적인 문제이다.
재귀함수 하나를 이용해서 가능한 수를 채워널어가면서 숫자를 더 넣지 못하면 되돌아가고, 끝까지 채웠으면 결과를 출력하면 된다.
vector<int> find_candidate(int i, int j)
는 (i, j) 좌표에 넣을 수 있는 숫자들을 벡터에 넣어서 반환하는 함수이다. 상하, 좌우, 3x3q 박스를 살펴본다.
이 candidates에 있는 후보들을 하나씩 table에 채워 넣고 재귀의 다음 depth로 보내본다. 만약 재귀가 도착점에 도달하지 못하고 return해서 돌아왔다면 그것은 실패한 경우의 수가 된다.
모든 candidate를 다 보내봤는데 전부 도착점에 도달하지 못하고 return해왔으면 이전 단계부터 글러먹은 것이니 table[i][j]를 초기화한 후 return한다. -
헤맨 부분
bool nums[9] = {false,};
에서 배열이 자동 초기화되는 줄 알고bool nums[9];
로 했다가 한참 틀렸다. undefined behavior가 나타나게 되는 것 같다.