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

서론

정답이 여러개가 나오면 전부 출력을 하는 문제가 있었는데, 발견이 쉽지 않았다.

다른분들의 코드에서 'exit(0)'을 발견하고 알아낼 수 있었다.

풀이

이 문제는 DFS 문제다.

처음 만나는 0의 좌표에 1~9까지 각각 넣어보고 조건에 맞으면 두번째 만나는 0도 1~9까지 넣어보고 이를 반복하다가 마지막에 만나는 0도 1~9까지 중 하나를 넣었더니 답을 만족하면 출력한다.

만약 두번째 만나는 0을 1~9까지 전부 넣어봤는데 조건에 맞는게 없다면 첫번째 만난 0에서 값을 잘못 넣은 것이므로 리턴하는 방식이다.

조건은 3개가 주어지는데 셋 다 함수로 만들고 리턴값은 boolean으로 줬다. 세 함수의 리턴값이 전부 true면 조건에 만족하므로 값을 넣으면 된다.

각 함수는 가로, 세로, 사각형에 안에 현재값과 같은 값이 존재하면 false를 리턴한다.

마지막 0까지 조건에 맞는 값을 넣었으면 출력을 해야하는데, 출력 후 그냥 return시키면 또 다른 정답이 있는지 계속 탐색하므로 강제로 프로그램을 종료해야한다.

스도쿠 값을 입력받을떄 0은 따로 벡터에 좌표를 저장해서 DFS에서 전 범위를 탐색하지 않게 했다.

구현

//c++

#pragma warning(disable:4996)
#include <vector>
#include <iostream>
#include <cstdio>

int map[10][10];
int zeroCnt;
std::vector<std::pair<int, int>>v;

void input() {
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			int x;
			scanf("%d", &x);
			if (x == 0) {
				v.push_back({ i, j }); 
				zeroCnt++;
			}
			else map[i][j] = x;
		}
	}
}

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

bool checkWidth(int y, int x, int value) {
	for (int i = 0; i < 9; i++) {
		if (map[y][i] == value) return false;
	}
	return true;
}

bool checkHeight(int y, int x, int value) {
	for (int i = 0; i < 9; i++) {
		if (map[i][x] == value) return false;
	}
	return true;
}

bool checkSquare(int y, int x, int value) {
	int startY = y - y % 3;
	int startX = x - x % 3;
	for (int i = startY; i < startY + 3; i++) {
		for (int j = startX; j < startX + 3; j++) {
			if (map[i][j] == value) return false;
		}
	}
	return true;
}

void dfs(int cnt) {
	if (cnt == zeroCnt) { 
		output();
		exit(0);
	}
	int y = v[cnt].first;
	int x = v[cnt].second;

	for (int i = 1; i <= 9; i++) {
		if (checkWidth(y, x, i) == true && checkSquare(y, x, i) == true && checkHeight(y, x, i) == true) {
			map[y][x] = i;
			dfs(cnt + 1);
			map[y][x] = 0;
		}
	}	
	return;
}

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