[백준/BOJ] 2580 스도쿠 - 접근과 풀이 (c++)

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

2580번: 스도쿠

n-queen 문제와 더불어 백트래킹의 기본이자 교과서같은 문제 라고 나혼자 정했다. js로 쿼리도 게임을 만들면서 bfs 백트래킹을 통해 최적의 위치를 찾아야 하는데, 백트래킹 하는 법을 까먹어서 급하게 다시 도전한 문제.

---

접근 방법

 

백트래킹이란게, 결국 완전탐색을 재귀적으로 하는 것이라고 나는 생각한다. 

앞에서부터 빈 칸을 1~9로 채워 나가는데, 해당 칸에 가능한 숫자인지 확인해주고, 가능하다면 재귀를 한단계 더 들어가는 것이다. 여기서 시간을 조금 줄이기 위해, 빈 칸을 탐색으로 찾지 않고 빈 칸의 좌표(row, col)를 담은 벡터를 하나 만들어서 사용했다. 

이렇게 적고보면 되게 쉬운데 그동안 왜 어렵다고 느꼈을까?

 

---

풀이

 

tag : back-tracking

 

#include<iostream>
#include<vector>
#define pii pair<int,int>
#define mp make_pair
using namespace std;
int arr[9][9];
int ansFlag=0;
vector<pii> v; //빈칸의 위치
int check(int r,int c){ //해당 칸에 가능한 숫자인지
  int num=arr[r][c];
  for(int row=0;row<9;row++){
    if(row==r)
      continue;
    if(arr[row][c]==num)
      return 0;
  }
  for(int col=0;col<9;col++){
    if(col==c)
      continue;
    if(arr[r][col]==num)
      return 0;
  }
  int row=r/3*3;
  int col=c/3*3;
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      int nr=row+i;
      int nc=col+j;
      if(nr==r && nc==c)
        continue;
      if(arr[nr][nc]==num)
        return 0;
    }
  } 
  return 1;
}
void recur(int idx){ //벡터의 인덱스
  if(v.size()==idx){
    //printf("%d idx end",idx);
    for(int i=0;i<9;i++){
      for(int j=0;j<9;j++){
        cout<<arr[i][j]<<" ";
      }
      cout<<endl;
    }
    ansFlag=1;
    return;
  }
  int r=v[idx].first;
  int c=v[idx].second;
  for(int i=1;i<=9;i++){
    arr[r][c]=i;
    if(check(r,c) && !ansFlag){
      recur(idx+1);
    }
    arr[r][c]=0;
  }
}
int main(){
  for(int i=0;i<9;i++){
    for(int j=0;j<9;j++){
      cin>>arr[i][j];
      if(arr[i][j]==0){
        v.push_back(mp(i,j));
      }
    }
  }

  recur(0);
}