[C++] 백준 2580번 : 스도쿠

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

2580번: 스도쿠

---

문제 풀이

 스도쿠의 특성상 전체 행, 열 그리고 9 분할된 3x3 박스 모두 값이 겹치지 않는지 확인해야 한다. 이 부분은 함수로 구현해서 따진다. 3x3 박스 영역은 입력받은 좌표를 3으로 나눈 값으로 따질 수 있다.

이후 1~9까지 값들을 빈 영역에다가 대입해보고 구현한 함수로 중복 여부를 따져본다. 중복이 없다면 다시 호출한다.

계속 값을 차례차례 확인하고 넘어가도 어떤 특정 좌표에서 어떤 경우도 성립하지 않는 경우는 다시 돌아간다.

느낀 점

체크하는 함수를 구현하는 것은 쉬웠다. 하지만 스도쿠 백트래킹 함수를 구현하는데 있어 어떤 값을 기준으로 할지 감을 못 잡아 생각보다 오래 걸렸다. 또한, 특정 자리에 값이 적절치 않을 경우를 생각하지 못해서 더 오래 걸렸다. 다음에 시간적 여유가 된다면 다시 구현해보고 싶다.

코드

#include <iostream>
#include <utility>
#include <vector>
#define MAX 9
using namespace std;

vector<pair<int, int>>points; // 빈칸의 좌표들
int board[MAX][MAX] = { 0, };
int cnt = 0;
bool flag = false;

bool check(pair<int, int> p) {
	int x_sec = p.first / 3; 
	int y_sec = p.second / 3;
	for (int i = 0; i < MAX;i++) { 
		if (board[p.first][p.second] == board[p.first][i] && i != p.second) return false; // 행 체크
		if (board[p.first][p.second] == board[i][p.second] && i != p.first) return false; // 열 체크
	}
	for (int i = 3 * x_sec; i < 3*x_sec + 3;i++) { // 3x3 박스 체크
		for (int j = 3 * y_sec; j < 3*y_sec + 3;j++) {
			if (board[p.first][p.second] == board[i][j] && (p.first != i && p.second != j))
				return false;
		}
	}
	return true;
}

void sudoku(int n) {
	if (n == cnt) {
		for (int i = 0; i < MAX;i++) {
			for (int j = 0; j < MAX;j++) {
				cout << board[i][j] << " ";
			}
			cout << "\n";
		}
		flag = true;
		return;
	}

	for (int i = 1; i <= MAX; i++) {
		board[points[n].first][points[n].second] = i;
		if (check(points[n])) sudoku(n + 1);
		if (flag) return;
	}

	board[points[n].first][points[n].second] = 0;
	return;
}


int main() {
	pair<int, int> point;
	for (int i = 0; i < MAX;i++) {
		for (int j = 0; j < MAX; j++) {
			cin >> board[i][j];
			if (board[i][j] == 0) {
				cnt++;
				point.first = i;
				point.second = j;
				points.push_back(point);
			}
		}
	}
	sudoku(0);
}