[BAEKJOON] 2580번 스도쿠

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

 

문제조건

1. 스도쿠판을 채우자
2. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
3. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

접근방법

 

문제를 보자마자 떠오른 생각은 N-Queen 문제와 상당히 유사한 문제라는 생각 이었다. 물론 Brute Force로 모든 경우의 수를 탐색해서 구할 수도 있겠지만, O(2^n) 이상의 시간소요로 시간초과가 날 것이 분명했고, N-Queen문제와 같이 백트래킹으로 접근했다.

유망한지 판단하고, 유망하다면 DFS를 진행하는 백트래킹 방식에서 시간단축이 됨을 인지하고, 가로, 세로, 3x3 크기의 칸에서 같은 숫자가 하나도 없는지 체크하고 그러면 유망한것으로 판단하고 DFS를 진행하도록 했다.

 

#include <iostream>
#include <vector>
using namespace std;

int map[10][10];
vector<pair<int, int> > v;
bool judge = false;
int res;

bool promising(pair<int ,int> p) {
	int x = p.first;
	int y = p.second;
	int divide_x = x / 3;
	int divide_y = y / 3;
	// 직선검사
	for (int i = 0; i < 9; i++) {
		if (map[x][i] == map[x][y] && i != y) return false;
		if (map[i][y] == map[x][y] && i != x) return false;
	}
	// 3x3 칸 검사
	for (int i = 3 * divide_x; i < 3 * divide_x + 3; i++)
		for (int j = 3 * divide_y; j < 3 * divide_y + 3; j++)
			if (map[i][j] == map[x][y] && i != x && j != y) return false;
	return true;
}

void dfs(int n) {
	if (n == res) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				cout << map[i][j] << " "; 
			}
			cout << '\n';
		}
		judge = true;
		return;
	}
	for (int i = 1; i <= 9; i++) {
		map[v[n].first][v[n].second] = i;
		if (promising(v[n])) dfs(n + 1);
		if (judge) return;
	}
	map[v[n].first][v[n].second] = 0;
	return;
}

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) {
				v.push_back({ i,j });
				res++;
			}
		}
	}
	dfs(0);

}

백트래킹의 정석같은 느낌의 문제였다.