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

스도쿠인데 스토쿠라고 항상 읽게 된다. 비슷한 단어는 스토킹인데, 헷갈릴만한가?

문제 바로가기

2580번: 스도쿠

---

개요

백준에서 단계별로 풀어보기를 쭉 이어나가다가 이 문제를 맞닥트렸다. 무려 골드4의 난이도를 자랑한다.

의외로 첫 풀이는 간단했다. 그냥 규칙을 적용했더니, 예제는 그냥 풀려버렸다.

그냥 빈 칸 마다 들어갈 수 있는 후보 하나를 쭉 대입하는 방식이었다.

하지만, 당연하게도 그건 답이 아니었다.

---

풀이

이 문제는 백트랙킹으로 분류된 만큼, 빈 칸에 들어갈 수의 후보가 하나가 아닐 수도 있다.

그래서 재귀함수를 구현했다.

기존 코드에서 큰 변화는 없고, 후보 마다 재귀호출을 해줬다.

코드를 검토하기 위해, 구글에서 스도쿠 고급 문제 여럿을 입력해봤다.

하지만, 아무런 출력이 없이 프로그램이 종료된다.

질문답변 게시판에서 반례 몇 개 찾아서 입력해보니, 이건 또 잘 출력된다.

그래서 그냥 제출했더니 맞았습니다!!

---

정답 코드

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; i++)
#define INF 987654321
#define EL "\n"

bool isEnd = false;
int table[9][9];
deque<pair<int, int>> blanks;

void solve() {
	if (blanks.empty()) {
		// VERIFY
		FOR(r, 9) FOR(c, 9)
			if (table[r][c] == 0)
				return;

		// SUCCESS
		isEnd = true;
		FOR(r, 9) {
			FOR(c, 9)
				cout << table[r][c] << " ";
			cout << EL;
		}
		exit(0);
	}

	auto [r, c] = blanks.front();
	bool CanBe[9];
	memset(CanBe, true, sizeof(bool) * 9);

	// ROW
	FOR(_c, 9)
		if (table[r][_c])
			CanBe[table[r][_c] - 1] = false;

	// COLUMN
	FOR(_r, 9)
		if (table[_r][c])
			CanBe[table[_r][c] - 1] = false;

	// SQUARE
	int _r = (r / 3) * 3;
	int _c = (c / 3) * 3;
	FOR(i, 3) {
		FOR(j, 3) {
			if (table[_r + i][_c + j])
				CanBe[table[_r + i][_c + j] - 1] = false;
		}
	}

	// RECURSION
	FOR(i, 9)
		if (CanBe[i]) {
			table[r][c] = i + 1;
			auto temp = blanks.front();
			blanks.pop_front();
			solve();
			blanks.push_front(temp);
			table[r][c] = 0;
		}
}

int main() {
	FAST_IO;

	FOR(r, 9) FOR(c, 9) {
		cin >> table[r][c];
		if (table[r][c] == 0)
			blanks.push_back(make_pair(r, c));
	}

	solve();

	return 0;
}

---

코드 설명

입력 단계에서 0이 입력되는 칸의 좌표(row, column)을 deque blanks에 저장하였다.

입력을 받은 후 solve 함수를 호출한다.

solve 함수에서 blanks.front()를 통해 한 좌표를 가져와 해당 칸에 들어갈 수 있는 값을 확인한다.

대입이 가능한 후보마다 칸에 대입하고, blanks.front()의 요소를 잠시 다른 곳에 옮겨둔 뒤 재귀호출을 해준다.

재귀호출이 끝난 후에는 칸의 값을 0으로 돌려놓고 blanks.front()의 요소를 다시 넣어준다.

solve 함수에 진입했을 때, blanks가 비어있다면 모든 빈 칸을 확인한 것이다.

이 때, 0인 칸이 있는지 확인합니다. 만약, 0인 칸이 있다면 정답에 도달하지 못 하였으므로 return을 한다.

그렇지 않다면 정답이므로, 해당 시점의 table을 출력하고 exit(0)을 통해 프로그램을 종료한다.