백준 알고리즘 2580번: 스도쿠 [C++]

문제 출처: www.acmicpc.net/problem/2580

2580번: 스도쿠

1. 코드

#include <iostream>

using namespace std;

typedef struct {
	int x;
	int y;
}Point;

int board[9][9] = { 0, };
int cnt = 0;				//board에 0이 입력된 횟수
Point p[162] = { 0, };			// board에 0이 입력된 좌표 저장

bool check(int x, int y, int key)
{
	for (int i = 0; i < 9; i++)
	{
		if (board[x][i] == key) return false; //세로 열 확인

		if (board[i][y] == key) return false; //가로 열 확인
	}
	for (int i = x / 3 * 3; i < x / 3 * 3 + 3; i++)
		for (int j = y / 3 * 3; j < y / 3 * 3 + 3; j++)
			if (board[i][j] == key)	//한 구역 당 숫자들 중 같은게 있다면
				return false;

	return true;
}

void solution(int a)
{
	if (a == cnt)
	{
		for (int i = 0; i < 9; i++)
		{
			for (int j = 0; j < 9; j++)
				cout << board[i][j] << " ";
			cout << endl;
		}
		exit(0);		//정상 종료
	}

	for (int j = 1; j < 10; j++)
	{
		if (!check(p[a].x, p[a].y, j)) continue;

		board[p[a].x][p[a].y] = j;
		solution(a + 1);
		board[p[a].x][p[a].y] = 0;
	}
}

int main(void)
{
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			cin >> board[i][j];
			
			if (!board[i][j])
			{
				p[cnt].x = i;	//0이 입력된 x좌표 저장
				p[cnt].y = j;	//0이 입력된 y좌표 저장
				cnt++;		//0이 입력된 횟수 증가
			}
		}
	}
	solution(0);
	return 0;
}

(실행)

2. 풀이

먼저 풀이 방식은 재귀를 이용한 백트래킹 방식으로 문제를 해결하였는데 0을 입력한 좌표를 기억을 한 뒤 그 좌표에만 접근하여 해당 위치에 1부터 9까지 중에서 조건에 해당하는 것만 board에 저장하는 방식이다. 그리고 board에 더 이상 0이 존재하지 않을 때 프로그램을 종료한다.

typedef struct {
	int x;
	int y;
}Point;

int board[9][9] = { 0, };
int cnt = 0;				//board에 0이 입력된 횟수
Point p[162] = { 0, };			// board에 0이 입력된 좌표 저장

먼저 main 함수 전에 Point라는 구조체를 선언했는데 이 구조체는 board에 0이 입력된 좌표를 저장하기 위한 구조체이고, board는 스도쿠 판을 의미한다. cnt는 0이 입력된 횟수를 의미하고 Point p[162]는 입력된 좌표가 총 9 × 9 × 2 = 162개 이기 때문에 구조체 배열로 선언하였다.

int main(void)
{
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			cin >> board[i][j];
			
			if (!board[i][j])
			{
				p[cnt].x = i;	//0이 입력된 x좌표 저장
				p[cnt].y = j;	//0이 입력된 y좌표 저장
				cnt++;		//0이 입력된 횟수 증가
			}
		}
	}
	solution(0);
	return 0;
}

그리고 main 함수 실행 시 바로 board에 수를 입력을 하고, 입력된 수가 0일 때 구조체 배열 p에 x좌표와 y좌표를 저장하고 cnt의 수를 1 증가시킨다. 그리고 solution(0)을 실행한다.

void solution(int a)
{
	if (a == cnt)
	{
		for (int i = 0; i < 9; i++)
		{
			for (int j = 0; j < 9; j++)
				cout << board[i][j] << " ";
			cout << endl;
		}
		exit(0);		//정상 종료
	}

	for (int j = 1; j < 10; j++)
	{
		if (!check(p[a].x, p[a].y, j)) continue;

		board[p[a].x][p[a].y] = j;
		solution(a + 1);
		board[p[a].x][p[a].y] = 0;
	}
}

a는 참조의 횟수이자 위치이다. 그래서 a와 cnt가 같으면 출력 후 exit(0) 정상 종료를 한다.  exit를 사용하여 프로그램을 종료하는 이유는 만약 여기서 함수를 반환하는 return을 사용하면 다른 경우의 수를 찾아서 계속 반복하지만 우리에게 필요한 것은 1가지 경우만 출력되면 상관이 없기 때문에 반환이 아닌 종료를 해준다.

a와 cnt가 같지 않다면 1부터 9까지의 수를 check를 통해 확인한 뒤 조건에 해당하는 것만 board에서 0이 입력된 위치에 입력이 되고, 재귀 함수를 호출한다. 재귀 함수가 종료하면 현재 저장되어 있는 board값이 아닌 다른 값을 입력해야 정답이 나오기에 board의 값을 0으로 초기화시켜준다.

bool check(int x, int y, int key)
{
	for (int i = 0; i < 9; i++)
	{
		if (board[x][i] == key) return false; //세로 열 확인

		if (board[i][y] == key) return false; //가로 열 확인
	}
	for (int i = x / 3 * 3; i < x / 3 * 3 + 3; i++)
		for (int j = y / 3 * 3; j < y / 3 * 3 + 3; j++)
			if (board[i][j] == key)	//한 구역 당 숫자들 중 같은게 있다면
				return false;

	return true;
}

check 함수에서는 0인 board의 좌표를 x, y에 전달받고 입력될 수로 key값으로 전달받는다. 그리고 해당 좌표의 행과 열 중 key 값에 해당하는 값이 있다면 false를 반환해주고 해당 좌표에 해당하는 구역의 요소 중 key값에 해당하는 값이 있다면 false를 반환해준다. 그 무엇도 해당되지 않으면 true를 반환한다.

3. 느낀 점

스도쿠를 한 번도 해보지 않아 이번에 처음 규칙을 봐서 조금 많이 헷갈려서 오래 걸렸지만 막상 코드를 짜고 보니 나름대로 간결해서 허탈한 느낌이 많이 든다.