개요

갑자기 왜 안쓰던 알고리즘 풀이를 쓰느냐 묻는다면 그냥 이번 문제 풀이가 깔끔했고 잘풀었기 때문입니다.

 

참고로 이번 문제 2239. 스도쿠는 11월에 푼 문제에요.

 

일자를 보면 G-STAR랑 겹치죠? 실제로 그 당시까지 1일 1백준을 지키기 위해 숙소에서 열심히 풀었습니다.

다음 날 숙소에서 앓아 눕지만 않았어도 스트릭이 깨질일은 없었을거에요.

 

 

 

문제

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

 

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

 

입력

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

 

출력

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

테스트케이스

입력 출력
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107		 143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

 

 

 

 

풀이

실버2 보다 높은 문제를 풀다보면 슬슬 '알고리즘 분류'를 보고 푸는게 훨씬 시간적으로도, 정신적으로도 편합니다.

가장 어려운 첫 시작에 추진력을 받을 수 있거든요.

그런 의미에서 이번 2239. 스도쿠의 알고리즘 분류는...

'백트래킹' 입니다.

 

백트래킹

백트래킹은 간단하게 '아님 말고'로 정의할 수 있습니다.

장난 아니고 진짜로요.

 

백트래킹, 한국어로는 퇴각검색. 킹무위키를 봤을때는 다음과 같이 설명합니다.

 

설명만 봤을때는 브루트포스와 상당히 비슷해보입니다.

하지만 브루트포스와 백트래킹은 결정적인 차이점이 하나 있습니다.

 

백트래킹은 현재 상태에서 다음 상태로 가는 모든 경우의 수를 고려하고, 만약 모든 경우의 수가 정답으로 가는 길과 멀어졌을때, 더 이상 유망하지 않을때 이전 상태로 돌아갑니다.

기본적으로 브루트포스처럼 모든 경우의 수를 탐색하되, 무차별적으로 모든 경우의 수를 탐색하는 것이 아니라 예외처리 과정을 거친다는 것이죠.

 

백트래킹은 DFS, BFS와도 연관이 깊습니다. DFS와 BFS 모두 범위를 벗어났다거나 특정 조건을 만족 못한 노드에 있다거나 하면 중간에 그냥 탈출 해버리곤 하잖아요? 특히 BFS 같은 경우는 백트래킹 그 자체라고 봐야합니다.

 

아이디어 정리

아무튼, 이 백트래킹을 스도쿠 문제에 대입해보자면 일단 9x9의 스도쿠 판에서 (0,0)부터 탐색을 해봅시다.

 

 

일단 내가 있는 칸에 이미 숫자가 들어가 있다면 다음 칸으로 이동해야겠죠.

 

 

만약 0이라면 아직 채우지 않은 칸이라는 뜻이니 해당 칸에 들어갈 수 있는 모든 숫자를 구합니다.

그 모든 숫자는 일단 해당 칸이 들어가 있는 3x3 크기의 박스와 같은 x, y축의 숫자를 검사해서 가져와야겠죠.

 

그리고 가져온 숫자를 정리해보면 (1,0)에 들어갈 수 있는 숫자는 4,7,8 입니다.

 

일단 저는 7이 맘에 드니 (1,0) 자리에 7을 넣고 다음 탐색으로 넘어가죠.

(3,0)의 자리엔 6밖에 들어갈 수 없습니다.

 

아무튼 쭉 이렇게 가다보면 (7,0)에서 문제가 생깁니다.

 

(7,0)에 들어갈 수 있는 숫자가 존재하지 않는거죠.

이럴때 백트래킹의 특성을 사용하는 것입니다. 모든 경우의 수가 더 이상 유망하지 않을때 이전 상태로 되돌아가는 것이죠.

가장 최근의 선택지인 (5,0)으로 되돌아갑니다.

하지만 (5,0)도 8 외의 선택지가 존재하지 않군요. 그러면 8 또한 유망하지 않은 선택지이므로 다시 뒤로 돌아갑니다.

 

2로 체킹해놨던 (4,0)의 자리로 돌아왔습니다. 

(4,0)엔 2와 8이라는 경우의 수가 존재했습니다. 저번에 2를 선택했으므로 이번엔 8을 선택하여 다시 다른 분기를 뻗어나갑니다.

 

뭐... 이렇게 무한반복해서 결국 답을 찾아내면 되겠죠. 딱봐도 탐색 모양새가 어떻습니까, 그냥 재귀 쓰라고 판을 깔아줬죠?

재귀... 써야겠지?

 

코드로 풀기

일단 스도쿠 판을 입력으로 주니까 받아야겠죠.

이런식으로 따닥따닥 붙어서 주어지기 때문에 string으로 받아줍시다.

string map[9];
for (int i = 0; i < 9; i++)
{
	cin >> map[i];
}

 

시작 전에 재귀함수 특성상 for문과 다르게 break가 불가능하기 때문에 만약 답을 다 찾았는데도 재귀를 빠르게 탈출하지 못할것을 고려해서 전역 bool 변수 하나만 두겠습니다.

bool finded = false;

만약 bool 변수가 없다면 이미 답을 찾았는데도 탐색 안한 곳까지 탐색을 모두 끝마쳐야 재귀를 탈출하기 때문에 필요합니다.

 

그리고 트래킹을 용이하게 하기 위해 간단하게 함수 2개를 만듭시다.

애초에 기본적으로 재귀 형태를 띄기 때문에 함수를 무조건 사용을 하긴 해야해요.

void tracking(int x, int y);
void nextTracking(int x, int y);

 

tracking은 이제 현재 내가 있는 칸을 씹고뜯고맛보고즐기는 함수입니다.

 

그리고 nextTracking은 내가 있는 칸을 주면 그 다음 칸의 tracking을 진행하는 그런 함수입니다.

현재 위치가 스도쿠 판을 벗어나면 그걸 교정해주는 역할을 맡습니다.

 

간단하게 nextTracking부터 구현해봅시다.

void nextTracking(int x, int y)
{
	int nextY = x + 1 == 9 ? y + 1 : y;
	int nextX = x + 1 == 9 ? 0 : x + 1;
	if (nextY == 9)
	{
		finded = true;
		return;
	}
	tracking(nextX, nextY);
}

일단 옆칸으로 이동하기 위해 x에 1을 더해주고 그 값이 범위를 벗어났다면 y를 1 올려주고 x를 0으로 초기화 한다는 뜻입니다.

또한 백트래킹 특성상 (8,8)에 도달하면 찾은거나 다름없기 때문에 finded를 true로 바꿔버린 다음 트래킹을 지속하지 않고 return 시켜버립니다.

 

이제 핵심인 tracking 함수를 구현...하기 전에 다른 함수부터 구현합시다. tracking 함수는 구현해 놓은 것들의 조각 모음이기 때문에 이것부터 설명하면 너무 의아해지기 때문에 위에서 말했던 해당 칸에 들어갈 수 있는 모든 숫자를 구하는 함수를 적어봅시다.

 

일단 간단하게 길이 9짜리 bool 배열을 놓고 모두 false로 초기화 합니다. 그리고 칸 기준으로 칸이 들어있는 3x3 박스, x, y축을 가져와 존재하는 숫자를 index로 놓고 배열에 접근하여 true로 바꿉니다.

그렇게 되면 이제 해당 칸에 들어갈 수 있는 숫자들만 false가 되겠죠? 이것을 이용할겁니다.

솔직히 제가 적고서도 너무 횡설수설이라 그냥 코드로 적어보겠습니다.

 

함수부터 선언해주고

vector<int> findPossibleNumbers(int x, int y);

 

배열을 다음과 같이 만들어줍니다.

bool numbers[9] = { false };

 

그리고 해당 칸을 기준으로 x축과 y축을 가져와서 0이 아닐경우 해당하는 숫자를 true로 체킹해줍니다.

for (int i = 0; i < 9; i++)
	if (map[i][x] != '0')
		numbers[map[i][x] - '1'] = true;
for (int i = 0; i < 9; i++)
	if (map[y][i] != '0')
		numbers[map[y][i] - '1'] = true;

'1'이나 '0'을 빼주는 이유는 map 배열이 string이기 때문입니다. int 2차원 배열이면 훨씬 보기 편하지만 귀찮아서 파싱작업을 굳이 안거쳤습니다.

 

그리고 3x3박스를 검사하기 위해 해당 칸을 담고 있는 3x3박스의 왼쪽 위 좌표를 구해줍니다.

int startX = x / 3 * 3;
int startY = y / 3 * 3;

 

그리고 탐색하면 끝이죠.

for (int i = startY; i < startY + 3; i++)
{
	for (int j = startX; j < startX + 3; j++)
	{
		if (map[i][j] != '0')
			numbers[map[i][j] - '1'] = true;
	}
}

 

그리고 numbers 배열을 순회하면서 false것만 vector에 담아 반환하면 끝입니다.

vector<int> possibles;
for (int i = 0; i < 9; i++) 
{
	if (!numbers[i]) 
	{
		possibles.push_back(i + 1);
	}
}
return possibles;

 

쉽죠? 사실 얘가 핵심이에요.

문제를 보면 오름차순이여야 한다는데 여기서 반환하는 숫자가 이미 정렬 되어있으면 됩니다.

이 방법은 자동으로 정렬도 돼요.

 

그리고 재귀를 돌면서 쓸데없이 값복사를 하지 않기 위해 간단한 place함수와 undo함수를 만들어줍니다.

void place(int x, int y, int n)
{
	map[y][x] = n + '0';
}

void undo(int x, int y)
{
	map[y][x] = '0';
}

 

 

이제 본체인 tracking 함수를 적어줍시다.

void tracking(int x, int y)
{
	if (finded) return;
	if (map[y][x] != '0') 
	{
		nextTracking(x, y);
		return;
	}

	vector<int> possibles = findPossibleNumbers(x, y);
	for (int n : possibles)
	{
		place(x, y, n);
		nextTracking(x, y);
		if (finded) return;
		undo(x, y);
	}
}

 

간단하죠?

 

그리고 이제 main함수를 적어줍시다.

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	for (int i = 0; i < 9; i++)
	{
		cin >> map[i];
	}

	tracking(0, 0);

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

 

tracking 함수 딸깍하면 끝입니다.

 

 

 

 

마치는 말

사실 1일 1백준은 끊긴지 오랩니다.

 

하지만 일이 너무 바빠서 어쩔 수 없었어요.(진짜임)

 

 

 

코드 전문

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <set>

using namespace std;

bool finded = false;
string map[9];

void tracking(int x, int y);
void nextTracking(int x, int y);
vector<int> findPossibleNumbers(int x, int y);
void place(int x, int y, int n);
void undo(int x, int y);

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	for (int i = 0; i < 9; i++)
	{
		cin >> map[i];
	}

	tracking(0, 0);

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


void nextTracking(int x, int y)
{
	int nextY = x + 1 == 9 ? y + 1 : y;
	int nextX = x + 1 == 9 ? 0 : x + 1;
	if (nextY == 9)
	{
		finded = true;
		return;
	}
	tracking(nextX, nextY);
}

void tracking(int x, int y) 
{
	if (finded) return;
	if (map[y][x] != '0') 
	{
		nextTracking(x, y);
		return;
	}

	vector<int> possibles = findPossibleNumbers(x, y);
	for (int n : possibles)
	{
		place(x, y, n);
		nextTracking(x, y);
		if (finded) return;
		undo(x, y);
	}
}

vector<int> findPossibleNumbers(int x, int y) 
{
	bool numbers[9] = { false };
	vector<int> possibles;
	for (int i = 0; i < 9; i++)
		if (map[i][x] != '0')
			numbers[map[i][x] - '1'] = true;
	for (int i = 0; i < 9; i++)
		if (map[y][i] != '0')
			numbers[map[y][i] - '1'] = true;
	int startX = x / 3 * 3;
	int startY = y / 3 * 3;
	for (int i = startY; i < startY + 3; i++)
	{
		for (int j = startX; j < startX + 3; j++)
		{
			if (map[i][j] != '0')
				numbers[map[i][j] - '1'] = true;
		}
	}
	for (int i = 0; i < 9; i++) 
	{
		if (!numbers[i]) 
		{
			possibles.push_back(i + 1);
		}
	}
	return possibles;
}

void place(int x, int y, int n)
{
	map[y][x] = n + '0';
}

void undo(int x, int y)
{
	map[y][x] = '0';
}

 

'알고리즘 > C++' 카테고리의 다른 글

[백준] | 골드5 달성!  (3) 2024.10.28
[백준] | C++ | 2869. 달팽이는 올라가고 싶다  (1) 2024.04.11
[백준] | C++ | 7785. 회사에 있는 사람  (1) 2024.03.31
[백준] | C++ | 9461. 파도반 수열  (1) 2024.03.20
[백준] | C++ | 1463. 1로 만들기  (2) 2024.03.17

티스토리툴바