[백준] 2580번 스도쿠 - C/C++

백준 2580 문제(Problem)

백준 2580 문제

풀이(Solution)

이 문제는 빈칸의 위치를 배열이나 벡터에 따라 저장해놔야겠다! 고 생각이 들었다면 So-easy 하게 풀 수 있는 문제이다.

필자는 빈칸의 위치를 v라는 벡터에 따로 담아두었고, 이를 이용한 백트래킹을 사용하였다. 

 

여기에서 사용한 함수는 func 함수와 check 함수이다. 각각 어떤 용도로 사용하였는지는 아래에 설명하겠다.

 

<func 함수>

void func(int n) {
  if(n==v.size()) { done=1; return; }

  int x=v[n].first, y=v[n].second;
  for(int i=1; i<=9; i++) {
    a[y][x]=i;
    if(check(x, y, i)) func(n+1);
    if(done) return; // 모두 채워졌기 때문에 함수 탈출~
  }
  a[y][x]=0;  // 백트래킹에서 원소를 다시 확인 할 때 값이 0이어야 하기 때문
}

위 함수는 백트래킹 알고리즘 기법을 사용한 함수이다. 함수를 재귀호출 할 때마다 n의 값을 증가하여 보내기 때문에 n의 값이 v(빈칸의 위치를 담은 벡터)의 길이와 같다는 것은 모두 탐색했다는 뜻이기에, done 변수를 1로 지정해주고 return 한다.

 

빈칸의 위치에 1부터 9까지 넣어보아 check 함수를 통해 가능 여부를 파악한 후, 가능하다면 func 함수를 재귀 호출해준다. 

a[y][x]=0을 해준 이유는 위의 주석과 같지만 이해를 돕기 위해서 사진을 첨부하겠다.

위와 같이 back을 할 때 0이 아닌 다른 숫자가 남아 있으면 안되기 때문에 0으로 초기화 하는 것이다.

 

 

<check 함수>

bool check(int x, int y, int v) {
  for(int i=0; i<9; i++) {
    if(a[y][i]==v && i!=x) return 0;
    if(a[i][x]==v && i!=y) return 0;
  }
  nx=int(x/3)*3, ny=int(y/3)*3;
  for(int i=ny; i<ny+3; i++) {
    for(int j=nx; j<nx+3; j++) {
      if(a[i][j]==v && i!=y && j!=x) return 0;
    }
  }
  return 1;
}

check 함수는 말 그대로 해당 위치에 값이 알맞게 들어갔는지 확인하는 함수이다. 

첫 번째 for문은 세로 가로 방향으로 탐색하여 가능하지 않은 위치이면 0을 반환하였다.

nx, ny는 해당 위치의 3x3 정사각형을 탐색할 수 있도록 nx와 ny를 0, 3, 6 의 원소들로 만들어 주어 탐색을 용이하게 만들었으며 가능하지 않은 위치이면 0을 반환하였다.

 

전체 코드(Code)

#include<iostream>
#include<vector>
using namespace std;
int a[9][9], nx, ny, done;
vector<pair<int ,int>> v;

bool check(int x, int y, int v) {
  for(int i=0; i<9; i++) {
    if(a[y][i]==v && i!=x) return 0;
    if(a[i][x]==v && i!=y) return 0;
  }
  nx=int(x/3)*3, ny=int(y/3)*3;
  for(int i=ny; i<ny+3; i++) {
    for(int j=nx; j<nx+3; j++) {
      if(a[i][j]==v && i!=y && j!=x) return 0;
    }
  }
  return 1;
}

void func(int n) {
  if(n==v.size()) { done=1; return; }

  int x=v[n].first, y=v[n].second;
  for(int i=1; i<=9; i++) {
    a[y][x]=i;
    if(check(x, y, i)) func(n+1);
    if(done) return;
  }
  a[y][x]=0;  // 백트래킹에서 원소를 다시 확인 할 때 값이 0이어야 하기 때문
}

int main() {
  for(int i=0; i<9; i++) {
    for(int j=0; j<9; j++) {
      cin >> a[i][j];
      if(a[i][j]==0) v.push_back({j, i});
    }
  }

  func(0);

  for(int i=0; i<9; i++)
    for(int j=0; j<9; j++)
      cout << a[i][j] << ' ';
    cout << '\n';
}