백준 2580 스도쿠

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

2580번: 스도쿠

학창시절 아빠 폰 게임으로 많이 한 스도쿠이다. 스도쿠를 생각해보면 두가지 조건이 있다.

 

조건

1. 가로, 세로 줄에 1 ~ 9까지의 모든 수가 한번씩 나와야 한다.

2. 해당 좌표가 위치한 3 * 3의 수 모두 겹치지 않고 1 * 9까지 나와야한다. 

 

다른 사람들의 코드도 살펴 본봐 DFS를 사용해서 모든 점을 방문 하듯이 풀었는데 필자는 0인 수의 좌표만을 이용해서 풀었다. 좌표룰 vactor에 담아뒀다가 backtracking의 limit을 vector의 개수만큼 체크해준다.

 

하지만 나는 이점이 1일 때 해당 좌표에서는 만족하는가 를 따져서 

 

yes -> 다음 정점에 올 점을 구했다.

 

No -> 다른 수가 되는지 체크했다. 

backtracking이라서 해당 결과가 끝나면 다시 되돌아와서 다른 정점을 테스트 해본다.

 

또 이문제에서 주의해야할 점이 있는데 한번만 출력을 한 후 프로그램을 바로 종료해줘야한다.

 

#include <cstdio>
#include <vector>

using namespace std;

vector<pair<int, int> > position;
int map[10][10];

void input();
void backTracking(int limit);
int isValidSdoko(int value, pair<int, int> position);

int main(){
	input();
	backTracking(0);
}

void input(){
	for(int y = 0; y < 9; y++){
		for(int x = 0; x < 9; x++){
			scanf("%d", &map[y][x]);
			if(!map[y][x])
				position.push_back(make_pair(y, x));
		}
	}
}

void backTracking(int limit){
	if(limit == position.size()){
		for(int y = 0; y < 9; y++){
			for(int x = 0; x < 9; x++){
				printf("%d ",map[y][x]);
			}
			printf("\n");
		}
		exit(0);
	}

	for(int number = 1; number <= 9; number++){
		if(isValidSdoko(number, position[limit])){
			int y = position[limit].first;
			int x = position[limit].second;
			map[y][x] = number;
			backTracking(limit+1);
			map[y][x] = 0;
		}
	}
}

int isValidSdoko(int value, pair<int, int> position){
	int yPos = position.first;
	int xPos = position.second;

	for(int x = 0; x < 9; x++)
		if(map[yPos][x] == value)
			return 0;

	for(int y = 0; y < 9; y++)
		if(map[y][xPos] == value)
			return 0;

	int threeStartY = position.first/3 * 3;
	int threeStartX = position.second/3 * 3;

	for(int y = threeStartY; y < threeStartY + 3; y++){
		for(int x = threeStartX; x < threeStartX + 3; x++){
			if(map[y][x] == value)
				return 0;
		}
	}

	return 1;
}