[백준 / C++] 스도쿠(골드4, 2580)

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

문제

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

 

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

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

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

 

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

 

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

 

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

입력

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

출력

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

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

제한

• 12095번 문제에 있는 소스로 풀 수 있는 입력만 주어진다.
  • C++14: 80ms
  • Java: 292ms
  • PyPy3: 1172ms

예제 입력 1

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

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

---

문제 풀이

이번 문제는 스도쿠의 빈 칸을 채우는 문제입니다.

 

스도쿠는 가로, 세로, 해당 칸이 포함된 3 x 3 공간에 같은수가 들어올 수 없습니다.

 

문제의 제한에 시간과 관련된 정보가 적혀있어서, 최대한 적은 양을 완탐으로 돌리고 싶었고 실제 스도쿠를 푸는 것과 같이 칸 별로 들어갈 수 있는 수들을 매핑해두고 해당 수들로만 완전탐색 알고리즘을 수행하였습니다.

 

추가적으로 제출하기 전 반례를 테스트해보기 위해 모두 0이 들어간 스도쿠를 입력해보았는데 중간중간 0이 포함된 결과를 확인했습니다.

 

즉, 1 ~ 9까지의 숫자 중 매핑된 숫자가 전부 아닌 경우 반드시 return을 해줘야 불가능한 경우를 건너뛰지 않으며, 값이 정확하게 나오게 됩니다.

 

스도쿠 문제는 문제 자체가 어렵기보다는 반례를 입력할 수가 없어서(모두 0을 넣는 것 외의 반례 만들기가 힘듬) 정답률이 낮은 것 같습니다.

코드

 

#include <iostream>
#include <vector>
#include <map>
#include <string.h>
using namespace std;

vector<int> adj[10];
vector<pair<int, int>> pos;

map<int, vector<int>> m;

bool visited[10];
bool allReturn = false;

void Print()
{
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			cout << adj[i][j] << " ";
		}
		cout << '\n';
	}
}

bool Check(int y, int x, int num)
{
	// y축, x축에 같은 숫자가 있는지 검사
	for (int i = 0; i < 9; i++)
	{
		if (adj[i][x] == num) return false;
		if (adj[y][i] == num) return false;
	}

	// 3 * 3 안에 같은 숫자가 있는지 검사
	int yIdx = (y / 3) * 3;
	int xIdx = (x / 3) * 3;

	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			if (adj[yIdx + i][xIdx + j] == num) return false;
		}
	}

	return true;
}

void Go(int cnt)
{
	if (cnt == pos.size())
	{
		Print();
		allReturn = true;
		return;
	}

	if (allReturn) return;

	for (int i = cnt; i < pos.size(); i++)
	{
		for (int j = 0; j < m[cnt].size(); j++)
		{
			if (Check(pos[i].first, pos[i].second, m[cnt][j]))
			{
				adj[pos[i].first][pos[i].second] = m[cnt][j];

				Go(cnt + 1);
				if (allReturn) return;
				adj[pos[i].first][pos[i].second] = 0;
			}
		}
		return;
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);


	vector<pair<int, int>> tempPos;

	// input
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			int temp;
			cin >> temp;

			if (temp == 0)
			{
				tempPos.push_back(make_pair(i, j));
			}

			adj[i].push_back(temp);
		}
	}


	// pos를 순회하며 들어갈 수 있는 요소들을 전부 저장하기
	for (int i = 0; i < tempPos.size(); i++)
	{
		memset(visited, true, sizeof(visited));
		vector<int> v;

		// 축 검사
		int y = tempPos[i].first;
		int x = tempPos[i].second;

		// * x축
		for (int j = 0; j < 9; j++)
		{
			if (j == x) continue;

			visited[adj[y][j]] = false;
		}

		// * y축
		for (int j = 0; j < 9; j++)
		{
			if (j == y) continue;

			visited[adj[j][x]] = false;
		}

		// * 3 x 3
		int yIdx = (y / 3) * 3;
		int xIdx = (x / 3) * 3;
		for (int j = 0; j < 3; j++)
		{
			for (int k = 0; k < 3; k++)
			{
				if (yIdx + j == y && xIdx + k == x) continue;

				visited[adj[yIdx+ j][xIdx + k]] = false;
			}
		}
		

		// 가능한 값 모두 넣기
		for (int j = 1; j <= 9; j++)
		{
			if (visited[j])
			{
				v.push_back(j);
			}
		}

		// 만약 가능한 숫자가1개라면?
		if (v.size() == 1)
		{
			// 그대로 적용해주도록 합니다.
			adj[y][x] = v[0];
		}
		// 아닌 경우
		else
		{
			// pos에 해당 값을 추가합니다.
			pos.push_back(tempPos[i]);
			// 맵에 추가하기
			m.insert(make_pair(pos.size() - 1, v));
		}
	}

	Go(0);
}