[백준 2580] 스도쿠

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

2580번: 스도쿠

#include <cstdio>
#include <vector>
int board[9 + 2][9 + 2];
int flag_row[9 + 2][9 + 2];
int flag_col[9 + 2][9 + 2];
int flag_cube[3 + 3][3 + 3][9 + 2];

struct _st
{
	int x;
	int y;
};

std::vector<_st> P;

void input(void)
{
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			scanf("%d", &board[i][j]);
			if (board[i][j] == 0) P.push_back({ i, j });
			else {
				flag_row[i][board[i][j]] = 1;
				flag_col[j][board[i][j]] = 1;
				flag_cube[i / 3][j / 3][board[i][j]] = 1;
			}
		}
	}
}

int chk(int x, int y, int num)
{
	if (flag_row[x][num]) return false;
	if (flag_col[y][num]) return false;
	if (flag_cube[x / 3][y / 3][num]) return false;
	return true;
}


int DFS(int n)
{
	if (n == P.size()) return true;

	int nx = P[n].x;
	int ny = P[n].y;

	for (int num = 1; num <= 9; num++) {
		if (!chk(nx, ny, num)) continue;

		flag_row[nx][num] = 1;
		flag_col[ny][num] = 1;
		flag_cube[nx / 3][ny / 3][num] = 1;
		board[nx][ny] = num;
		if (DFS(n + 1)) return true;
		flag_row[nx][num] = 0;
		flag_col[ny][num] = 0;
		flag_cube[nx / 3][ny / 3][num] = 0;
	}
	return false;
}


void output(void)
{
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			printf("%d ", board[i][j]);
		}
		printf("\n");
	}
}

int main()
{
	input();
	DFS(0);
	output();
	return 0;
}

스도쿠... ㅂㄷㅂㄷ 풀었던 문젠데 디버깅때문에 한시간을 쓰다니... 분하다

실제로 해본적이 없어서 가로랑 정사각형만 확인하면 되는줄 알고 틀렸었다. 세로도 확인해야 하더라고요 ... ? 

 

// input( ) 함수

9 * 9 스토쿠 판을 입력받을 때, 0인 부분에 숫자를 채워야 한다. 그래서 board[i][j] == 0인 좌표 (i, j)를 벡터에 저장하여 n번째 좌표의 숫자를 찾는 DFS를 작성해주려고 했다. 

그리고 i행에서 입력받은 숫자를 사용했음을 표시하기 위해 flag_row 배열을 두었다. 같은 용도로 flag_col 배열을 두어 j열에서 입력받은 숫자를 사용했음을 표시했다. flag_cube 행렬은 정사각형 내에서도 1부터 9까지의 수를 중복 사용할 수 없기 때문에 같은 용도로 선언하였다. 이때 (i / 3, j / 3)를 해준 이유은 9 * 9 행렬에서 3 * 3 정사각형이 9개 나오기 때문이다. 

like this..

// chk( ) 함수

해당 행 / 열 / 큐브에서 지금 삽입하려는 숫자를 사용했는지 여부를 체크하는 함수이다. 

하나라도 참이면 이미 그 숫자는 사용된 것이므로 false를 리턴한다. 세 가지 플래그 배열에서 모두 사용되지 않았다면 true를 리턴하여 보드의 빈 공간에 해당 숫자를 넣어준다. 

 

 

// DFS( ) 함수

넘겨준 파라미터는 "벡터의 몇번째 좌표값을 채울지" 이다. 

그리고 인덱스 0부터 시작했기 때문에, 만약 n이 벡터의 사이즈와 같아진다면 빈 공간을 모두 채운 것이므로 true를 리턴한다. 이렇게 DFS의 리턴값을 int로 해준 이유는, 가능한 모든 경우의 수를 찾아야 하는 것이 아니기 때문이다. 빈 공간을 모두 채우는 단 한가지의 경우의 수가 나오면 재귀함수를 종료해도 된다. 

이러한 맥락에서 만약 DFS(n + 1)의 리턴값이 false이면, 더 이상 재귀 호출을 진행하지 않는다.