[BOJ]2580번: 스도쿠 (c++)

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

2580번: 스도쿠

 

백트랙킹으로 적합한 숫자 채워나가기

#include <iostream>

using namespace std;

const int N = 9;
bool vert[N][N + 1];
bool hori[N][N + 1];
bool box[N][N + 1];
int sdoku[N][N];

// 스도쿠 프린트
void print_sdoku()
{
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			cout << sdoku[i][j] << ' ';
		}
		cout << '\n';
	}
}

bool go(int num)
{
	// 마지막 칸까지 모두 채우면 프린트 후 종료
	if (num == N * N)
	{
		print_sdoku();
		return true;
	}

	// 행/열/박스 n번째인지 구하기
	int x = num / N;
	int y = num % N;
	int idx = (x / 3) * 3 + (y / 3);

	// 빈칸이 아니면 바로 다음칸으로 go재귀함수 호출
	if (sdoku[x][y] != 0)
	{
		return go(num + 1);
	}
	// 빈칸이면
	else
	{
		/*
			1 ~ 9까지의 숫자 중에서
			행/열/박스 bool배열에서 공통적으로 false인 숫자를 빈칸에 저장하고
			각 배열의 해당 숫자에 true 체크한 후 go 재귀함수 호출
		*/
		for (int k = 1; k <= N; ++k)
		{
			if (!(vert[x][k] || hori[y][k] || box[idx][k]))
			{
				sdoku[x][y] = k;
				vert[x][k] = hori[y][k] = box[idx][k] = true;
				
				// 한번이라도 마지막칸에 도달했다면 종료
				if (go(num + 1))
				{
					return true;
				}
				sdoku[x][y] = 0;
				vert[x][k] = hori[y][k] = box[idx][k] = false;
			}
		}
	}
	return false;
}

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

	// 입력
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			cin >> sdoku[i][j];

			/*
				빈칸이 아니라면
				행/열/박스 bool배열에 true 체크하기
			*/
			if (sdoku[i][j] != 0)
			{
				int idx = (i / 3) * 3 + (j / 3);
				box[idx][sdoku[i][j]] = true;
				vert[i][sdoku[i][j]] = true;
				hori[j][sdoku[i][j]] = true;
			}
		}
	}

	// 완성 스도쿠를 구한 후 출력하기
	go(0);

	return 0;
}

 

 

재귀함수 go에서 매번 전체 스도쿠를 검사하는 식으로 짰더니 시간초과가 났다.

사실 이러면 while(left) 식으로, 빈칸이 남을 동안 while 반복문을 돌리는 것과 같아서

속도 고려를 전혀 안한 코드가 된다.

 

 

따라서 위에서부터 적합한 숫자를 채워나가고

만약 적합하지 않다면 원복한 후, 다음 숫자를 집어넣고

다시 진행하는 백트랙킹 방식이 적절하다.

이러면 이미 확실하게 정해진 앞부분을 불필요하게 다시 검사할 필요가 없다.

 

 

스도쿠는 가로/세로/ 3*3 크기의 박스 이렇게 3개의 bool배열이 필요하다.

따라서 bool 체크시에 3개의 배열 모두를 체크해줘야 하는 것을 잊지 말아야 한다.

 

 

시간 복잡도가 궁금해서 검색해봤더니 아래와 같은 답변이 있었다. 어쩐지 어렵더라..

이런 코드는 상한선을 적당히 계산할 수는 있겠지만 보드의 상태에 따라 너무나 많은 커팅이 일어나기 때문에 실제로 도는 속도와는 비교가 불가능할 것 같습니다. 커팅이 없다고 가정했을 때 각 줄에서 선택할 수 있는 수가 9가지씩이라고 가정하면 9^81이지만 실제로는 같은 행, 열, 3x3 사각형 내에 같은 수가 없는지를 체크하고 잘라내는 일들이 너무나 예측할 수 없게 발생하기 때문에 이 상한선은 크게 의미가 없습니다.

https://en.wikipedia.org/wiki/... 에서도 백트래킹 기법에 대해 설명하고 있지만 시간복잡도에 대한 이야기는 하지 않습니다.

 

 

https://www.acmicpc.net/board/view/31556

글 읽기 - 시간복잡도 계산이 잘안되네요...