[백준 C++] 2239번 스도쿠

1. 문제

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

2239번: 스도쿠

 

2. 알고리즘 분류

• 구현
• 백트래킹

 

3. 소스 코드

#include <stdio.h>
#include <vector>

using namespace std;

int map[9][9], blank_cnt;
bool is_end = false;
vector<pair<int, int>> blank;

// 가로 방향으로 해당 값이 들어갈 수 있는지 확인하는 함수
int check_horizontal(int y, int val)
{
	for (int x = 0; x < 9; x++) 
		if (map[y][x] == val) return 1;

	return 0;
}

// 세로 방향으로 해당 값이 들어갈 수 있는지 확인하는 함수
int check_vertical(int x, int val)
{
	for (int y = 0; y < 9; y++)
		if (map[y][x] == val) return 1;

	return 0;
}

// 정사각형 모형에 해당 값이 들어갈 수 있는지 확인하는 함수
int check_square(int y, int x, int val)
{
	int square_y = y / 3;
	int square_x = x / 3;

	for (int my = 3 * square_y; my < 3 * (square_y + 1); my++)
		for (int mx = 3 * square_x; mx < 3 * (square_x + 1); mx++)
			if (map[my][mx] == val) return 1;

	return 0;
}

// 현재 Map을 출력하는 함수
void print_map()
{
	for (int y = 0; y < 9; y++)
	{
		for (int x = 0; x < 9; x++)
		{
			printf("%d", map[y][x]);
		}
		printf("\n");
	}
}

// DFS 알고리즘
void dfs(int cur)
{
	// 답을 찾았다면 끝내기 (중복 답 출력 방지)
	if (is_end) return;

	// 빈 칸을 다 채웠다면 끝내기
	if (cur == blank_cnt)
	{
		print_map();
		is_end = true;
		return;
	}

	// 현재 빈칸 위치 파악
	int cur_y = blank[cur].first;
	int cur_x = blank[cur].second;

	// 1 ~ 9까지 값이 들어갈 수 있는지 확인한 후, Map에 저장한 후, 재귀 동작
	for (int i = 1; i <= 9; i++)
	{
		if (check_horizontal(cur_y, i)) continue;
		if (check_vertical(cur_x, i)) continue;
		if (check_square(cur_y, cur_x, i)) continue;

		map[cur_y][cur_x] = i;
		dfs(cur + 1);
		map[cur_y][cur_x] = 0;	// 위의 DFS에서 답을 찾지 못했다면, 다시 0으로 초기화
	}
}

int main()
{
	// Map 입력
	for (int y = 0; y < 9; y++)
	{
		char str[10];
		scanf("%s", str);

		for (int x = 0; x < 9; x++)
		{
			int tmp_num = str[x] - '0';
			map[y][x] = tmp_num;
			if (tmp_num == 0) blank.push_back({ y, x });
		}
	}

	// 빈 칸의 갯수 저장(빈 칸 다 채웠는지 여부 확인용)
	blank_cnt = blank.size();

	// DFS 알고리즘
	dfs(0);

	return 0;
}

 

4. 유용한 문법 / 알고리즘

 4-1) DFS 알고리즘(깊이 우선 탐색)

• 깊은 부분을 우선적으로 탐색하는 알고리즘
• 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사
• 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택

// DFS 알고리즘
void dfs(int cur)
{
	// 답을 찾았다면 끝내기 (중복 답 출력 방지)
	if (is_end) return;

	// 빈 칸을 다 채웠다면 끝내기
	if (cur == blank_cnt)
	{
		print_map();
		is_end = true;
		return;
	}

	// 현재 빈칸 위치 파악
	int cur_y = blank[cur].first;
	int cur_x = blank[cur].second;

	// 1 ~ 9까지 값이 들어갈 수 있는지 확인한 후, Map에 저장한 후, 재귀 동작
	for (int i = 1; i <= 9; i++)
	{
		if (check_horizontal(cur_y, i)) continue;
		if (check_vertical(cur_x, i)) continue;
		if (check_square(cur_y, cur_x, i)) continue;

		map[cur_y][cur_x] = i;
		dfs(cur + 1);
		map[cur_y][cur_x] = 0;	// 위의 DFS에서 답을 찾지 못했다면, 다시 0으로 초기화
	}
}