BOJ 2239. 스도쿠

🙇‍♀️[Gold IV] 스도쿠 - 2239

문제 링크

성능 요약

메모리: 2024 KB, 시간: 568 ms

분류

백트래킹, 구현

제출 일자

2024년 2월 22일 10:32:44

문제 설명

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

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

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

입력

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

출력

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

🚀풀이

백트래킹 문제로 DFS를 이용했다.

문제의 빈 칸에 1~9의 값을 모두 대입하여 정답의 경우를 찾아야한다.

int board[9][9]; // 스도쿠 보드 선언
vector<pair<int, int>> points; // 빈칸의 위치 저장
int cnt = 0;
bool found = false; // 스도쿠 판 완성 플래그

전역변수는 이렇게 잡았고 입력 값을 받는다.

void solve()
{
	pair<int, int> point;
	for (int i = 0; i < 9; i++)
	{
		string str;
		cin >> str;
		for (int j = 0; j < 9; j++)
		{
			board[i][j] = str[j] - '0';
			if (board[i][j] == 0)
			{
				cnt++;
				point.first = i;
				point.second = j;
				points.push_back(point); // 빈칸의 좌표 저장
			}
		}
	}

	sudoku(0);
}

sudoku함수가 DFS이다.

void sudoku(int N)
{
	if (N == cnt) // 빈칸의 개수만큼을 채워서 스도쿠 판이 완성되면
	{
		for (int i = 0; i < 9; i++) 
		{
			for (int j = 0; j < 9; j++)
			{
				cout << board[i][j];
			}
			cout << '\n';
		} // 결과 출력

		found = true; // 플래그 true로 변경

		return;
	}
	for (int j = 1; j <= 9; j++)
	{
		board[points[N].first][points[N].second] = j; // 1~9 까지의 숫자를 넣어봄
		if (check(points[N])) // 결과가 유효하면 다음 빈칸을 채우러 감
			sudoku(N + 1);
		if (found) // 스도쿠가 완성됬을경우 더 이상 다른 해를 찾을 필요가 없으므로 함수 종료
			return;
	}

	board[points[N].first][points[N].second] = 0;// 최적해를 못찾았을 경우 값 비워주기
	return;
}

한 칸의 값을 대입할 때 정답이 되는지 확인하는 함수로 check함수이다.

bool check(pair<int, int> p)
{
	int square_x = p.first / 3; // 구역을 나눔
	int square_y = p.second / 3;

	for (int i = 0; i < 9; i++)
	{
		if (board[p.first][i] == board[p.first][p.second] && i != p.second)
			return false; // 같은 행에 같은 숫자가 있으면 false 반환
		if (board[i][p.second] == board[p.first][p.second] && i != p.first)
			return false; // 같은 열에 같은 숫자가 있으면 false 반환
	}

	for (int i = 3 * square_x; i < 3 * square_x + 3; i++)
	{
		for (int j = 3 * square_y; j < 3 * square_y + 3; j++)
		{
			if (board[i][j] == board[p.first][p.second])
			{
				if (i != p.first && j != p.second)
					return false; // 같은 구역에 같은 숫자가 있으면 false 반환
			}
		}
	}

	return true; // 모든 조건 만족시 유효성 검사 통과
}

DFS에서 최적해를 찾지 못하였을 때 값을 다시 0으로 세팅해야한다.

처음에 0으로 되어 있는 부분을 1~9까지 다 채우고 전체가 정답이 되는지 확인하면서 문제를 풀려고 헀는데 시간이 너무 오래 걸려서 풀지 못했다.

이렇게 하나하나 세팅하면서 문제를 풀어야한다.

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;
int board[9][9]; // 스도쿠 보드 선언
vector<pair<int, int>> points; // 빈칸의 위치 저장
int cnt = 0;
bool found = false; // 스도쿠 판 완성 플래그

bool check(pair<int, int> p)
{
	int square_x = p.first / 3; // 구역을 나눔
	int square_y = p.second / 3;

	for (int i = 0; i < 9; i++)
	{
		if (board[p.first][i] == board[p.first][p.second] && i != p.second)
			return false; // 같은 행에 같은 숫자가 있으면 false 반환
		if (board[i][p.second] == board[p.first][p.second] && i != p.first)
			return false; // 같은 열에 같은 숫자가 있으면 false 반환
	}

	for (int i = 3 * square_x; i < 3 * square_x + 3; i++)
	{
		for (int j = 3 * square_y; j < 3 * square_y + 3; j++)
		{
			if (board[i][j] == board[p.first][p.second])
			{
				if (i != p.first && j != p.second)
					return false; // 같은 구역에 같은 숫자가 있으면 false 반환
			}
		}
	}

	return true; // 모든 조건 만족시 유효성 검사 통과
}
void sudoku(int N)
{
	if (N == cnt) // 빈칸의 개수만큼을 채워서 스도쿠 판이 완성되면
	{
		for (int i = 0; i < 9; i++) 
		{
			for (int j = 0; j < 9; j++)
			{
				cout << board[i][j];
			}
			cout << '\n';
		} // 결과 출력

		found = true; // 플래그 true로 변경

		return;
	}
	for (int j = 1; j <= 9; j++)
	{
		board[points[N].first][points[N].second] = j; // 1~9 까지의 숫자를 넣어봄
		if (check(points[N])) // 결과가 유효하면 다음 빈칸을 채우러 감
			sudoku(N + 1);
		if (found) // 스도쿠가 완성됬을경우 더 이상 다른 해를 찾을 필요가 없으므로 함수 종료
			return;
	}

	board[points[N].first][points[N].second] = 0;// 최적해를 못찾았을 경우 값 비워주기
	return;
}

void solve()
{
	pair<int, int> point;
	for (int i = 0; i < 9; i++)
	{
		string str;
		cin >> str;
		for (int j = 0; j < 9; j++)
		{
			board[i][j] = str[j] - '0';
			if (board[i][j] == 0)
			{
				cnt++;
				point.first = i;
				point.second = j;
				points.push_back(point); // 빈칸의 좌표 저장
			}
		}
	}

	sudoku(0);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}