BOJ 2580 - 스도쿠

www.acmicpc.net/problem/2580

2580번: 스도쿠

 

처음에는 아래 코드 처럼 푼게 아니라

이차원 배열을 이중포문으로 순회하면서 0 인 지점이 나타나면

백트래킹 함수로 진입하여 

백트래킹 함수 내에서 가로줄에 쓰인 숫자, 세로줄에 쓰인 숫자, 현재 좌표가 소속된 3 * 3 크기의 정사각형에 쓰인 숫자를 찾아내서 가능한 숫자들을 추려낸뒤에, 가능한 숫자들을 가지고 현재좌표에 백트래킹을 시도하는 방식으로 하려고 했다. 

(마치 아래 블로그 분과 유사한 느낌으로 접근하려 했다)

melonicedlatte.com/algorithm/2018/02/08/172524.html

[백준] 2580번 C/C++ 풀이 _ 스도쿠 - Easy is Perfect

 

 

그러나, 백트래킹 함수에 진입한 후에 어떤식으로 다음좌표로 넘어갈지가 애매했고,

위의 블로그분 같은 풀이도 아주 훌륭한 풀이지만, 

메인함수에서 이미 이중 포문으로 0이 아닌것을 찾아내서 다음 좌표로 이동하고 있는데

백트래킹 함수에서 또 다시 다른 이동 좌표를 찾아낸다는것은 중복된 계산을 하는 것 같다는 느낌이 들었다.

 

 

아래 블로그 글 처럼 다르게 푸신분들의 풀이를 보니, 전체 행렬이 9 * 9 행렬이니

총 가능한 원소의 갯수가 81개이고, 백트래킹 함수의 최대 깊이 값을 81로 설정하여,

프로그램을 종료시키는 형식으로. 푸는것이 더 깔끔한 코드라 느껴졌다.

백트래킹 재귀함수의 깊이 값에 따른 좌표 설정은 

int y = depth / 9, x = depth % 9; 로 찾아 낼 수 있으며, 

해당 좌표가 몇번째 사각형에 소속된지는, (y / 3) * 3 + (x / 3) 을 해보면 구할 수 있다

(위 식은 직접 좌표 예제 몇개 잡아서 해보면 금방 나온다)

또한 사용된 숫자를 찾는 방법은 위의 블로그 글 처럼 

일차원 배열 선언해서 행 탐색하고, 열 탐색하고, 소속된 사각형 탐색해서 정리해주는 것도 있지만

메모리를 더 쓰는 대신 코드가 간결해지려면 아래 블로그와 같은 글이 더 적합해 보였다.

yabmoons.tistory.com/88

[ 백준 2580 ] 스도쿠 (C++)

 

- c++

 

#include <iostream>
 
using namespace std;
 
int map[9][9];
int row[9][10];
int col[9][10];
int square[9][10];
 
void print_map() {
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            cout << map[i][j] << " ";
        }
        cout << "\n";
    }
}
 
void backtracking(int depth) {
    if (depth == 81) {
        print_map();
        exit(0);
    }
    
    int y = depth / 9, x = depth % 9;
    
    if(!map[y][x]) {
        for (int i = 1; i <= 9; ++i) {
            if (!row[y][i] && !col[x][i] && !square[(y / 3) * 3 + (x / 3)][i]) {
                map[y][x] = i;
                row[y][i] = true;
                col[x][i] = true;
                square[(y / 3) * 3 + (x / 3)][i] = true;
                backtracking(depth + 1);
                map[y][x] = 0;
                row[y][i] = false;
                col[x][i] = false;
                square[(y / 3) * 3 + (x / 3)][i] = false;
            }
        }
    } else {
        backtracking(depth + 1);
    }
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            cin >> map[i][j];
            if (map[i][j]) {
                row[i][map[i][j]] = true;
                col[j][map[i][j]] = true;
                square[(i / 3) * 3 + (j / 3)][map[i][j]] = true;
            }
        }
    }
    
    backtracking(0);
    
    return 0;
}