[백준 / BOJ] 2580번: 스도쿠

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

2580번: 스도쿠

 

 

---

 

 

문제

---

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.

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

위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

 

입력

---

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

 

출력

---

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

 

예제 입력

---

0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0

 

예제 출력

---

1 3 5 4 6 9 2 7 8
7 8 2 1 3 5 6 4 9
4 6 9 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
8 7 4 9 1 3 5 2 6
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
2 5 8 3 9 4 7 6 1

 

코드 

---

1) priority_queue 사용

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

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int v[9][9];
bool flag = false;

bool can_fill(int x, int y, int item) {
	for (int i = 0; i < 9; i++) {
		if (v[x][i] == item) return false;
		if (v[i][y] == item) return false;
	}
	int tmp_x = (x / 3) * 3;
	int tmp_y = (y / 3) * 3;
	for (int i = tmp_x; i < tmp_x + 3; i++) {
		for (int j = tmp_y; j < tmp_y + 3; j++) {
			if (v[i][j] == item) return false;
		}
	}
	return true;
}

void solve(int x, int y) {
	if (flag) return;
	if (pq.size() == 0) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				cout << v[i][j] << ' ';
			}
			cout << endl;
		}
		flag = true;
		return;
	}

	pq.pop();
	for (int i = 1; i <= 9; i++) {
		if (can_fill(x, y, i)) {
			v[x][y] = i;
			int nx = 0, ny = 0;
			if (pq.size() > 0) {
				nx = pq.top().first;
				ny = pq.top().second;
			}
			solve(nx, ny);
		}
	}
	v[x][y] = 0;
	pq.push({ x, y });
}

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

	int nx = 0, ny = 0;
	if (pq.size() > 0) {
		nx = pq.top().first;
		ny = pq.top().second;
	}
	solve(nx, ny);
	return 0;
}

 

2) 수정 코드

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

vector<pair<int, int>> zeros;
int v[9][9];
bool flag = false;

bool can_fill(int x, int y, int item) {
	for (int i = 0; i < 9; i++) {
		if (v[x][i] == item) return false;
		if (v[i][y] == item) return false;
	}
	int tmp_x = (x / 3) * 3;
	int tmp_y = (y / 3) * 3;
	for (int i = tmp_x; i < tmp_x + 3; i++) {
		for (int j = tmp_y; j < tmp_y + 3; j++) {
			if (v[i][j] == item) return false;
		}
	}
	return true;
}

void solve(int cnt) {
	if (flag) return;
	if (cnt == zeros.size()) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				cout << v[i][j] << ' ';
			}
			cout << endl;
		}
		flag = true;
		return;
	}

	int x = zeros[cnt].first;
	int y = zeros[cnt].second;

	for (int i = 1; i <= 9; i++) {
		if (can_fill(x, y, i)) {
			v[x][y] = i;
			solve(cnt + 1);
		}
	}
	v[x][y] = 0;
}

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

	solve(0);
	return 0;
}

 

---

 

 

첨에 구현했던 코드는 한 줄에 빈칸이 하나라고 가정하고 구현한 코드였다. 잘못 작성한 것을 깨닫고 좀 자고옴 >.0

30%에서 오류가 났었는데, 정답 값을 출력 한 후에도 재귀호출로 인해 여러 번 반복해서 출력이 돼서 그런가 싶어 flag를 두었더니 해결되었다. 

 

일단 값이 0인 모든 좌표들을 탐색하며 알맞은 값을 채우는 문제이다.

즉, 특정 좌표 x, y에 특정 값 v를 채울 수 있는지에 관한 문제인 것이다.

 

특정 좌표 x, y에 특정 값 v를 채울 수 있는가?

해당 좌표에 값 v를 부여할 수 있는지 판단하기 위해서는 해당 좌표의 가로방향, 세로방향, 그리고 해당 좌표가 속하는 3x3 정사각형 영역 내에 v가 없어야 한다. 하나라도 존재한다면 v를 부여할 수 없다.

 

 

처음에는 우선순위 큐를 값이 0인 좌표들을 보관하기 위한 자료구조로 사용하였다. 좌표들이 내림차순으로 정렬되기 때문에 가장 앞 원소를 넣었다 뺐다 하며 탐색했다. pq의 가장 앞에 있는 원소를 pop한 후 해당 좌표에 1~9의 값을 부여하며 탐색한다.  탐색 완료 후 다시 해당 좌표를 push하여 다음 탐색에 지장을 받지 않도록 해주었다. 

 

처음 작성한 solve 함수의 인자는 탐색할 칸의 x좌표, y좌표였다. 음.. 아무튼 이 코드는 pq가 비어있는 것을 생각해주며 파라미터에 값을 넘겨줘야 해서 살짝 어설프다는 생각이 들었다.

 

후에 인터넷 서칭을 통해 인자를 0의 갯수로 두도록 코드를 수정했다. 또한 pq를 통해 0의 좌표를 넣었다 뺐다 하며 pq의 사이즈가 0일때 리턴하는 식으로 하지 않고, vector 자료구조에 값이 0인 좌표를 넣어놓고 cnt를 통해 접근할 수 있도록 바꾸었다. 코드도 간결해지고 좀 더 빨라짐!