[C++] 백준 2580. 스도쿠

문제

입출력

풀이

스도쿠는 어릴 때 엄마한테 배웠는데 엄만 여전히 스도쿠를 하신다..
옆에서 보고 있으면 경이로운 수준이다
지뢰찾기 다시 좀 해야되나

하여간 이 문제는 전에 푼 n-queen과 흡사한 풀이 방식을 갖는다.
비어있는(채워야하는) 좌표를 벡터에 저장해두었다가
dfs를 돌며 모든 벡터를 다 쓰면(벡터 크기만큼 돌면)
풀어오던 배열을 출력하고 끝낸다.

dfs 함수에서 idx는 벡터에 저장된 좌표의 index값이며
모든 벡터를 다 돌면 flag를 두어 빠르게 return 하도록 했다.
해당 idx의 좌표에 들어갈 수 있는 숫자를 check하고,
돌다가 말 수도 있기 때문에 dfs가 끝나면 값을 돌려(0)준다.

check 함수에서는 같은 행에 혹은 열에 해당 숫자가 있는지
또 3 고바기 3 배열 안에 채우려는 숫자가 있는지 확인하며
걸리면 죽음이고 모든 기준을 통과하면 true를 return 한다.

코드

#include <iostream>
#include <vector>
using namespace std;

int arr[9][9];
bool flag;
vector<pair<int, int>> v;

bool check(int y, int x, int num) {
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			if (arr[y][j] == num || arr[i][x] == num) return false;
		}
	}
	int ny = (y / 3) * 3;
	int nx = (x / 3) * 3;
	for (int i = ny; i < ny + 3; i++) {
		for (int j = nx; j < nx + 3; j++) {
			if (arr[i][j] == num) return false;
		}
	}
	return true;
}

void dfs(int idx) {
	if (flag) return;
	if (idx == v.size()) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				cout << arr[i][j] << " ";
			}
			cout << "\n";
		}
		flag = true;
		return;
	}
	int y = v[idx].first;
	int x = v[idx].second;
	for (int i = 1; i <= 9; i++) {
		if (check(y, x, i)) {
			arr[y][x] = i;
			dfs(idx + 1);
			arr[y][x] = 0;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 0) v.push_back({ i, j });
		}
	}
	dfs(0);
	return 0;
}

채점

알고리즘을 제법 꾸준히 풀다가 사프 핑계로 쉬었더니
갑자기 이유를 알 수 없는 잔디 탈모가 생겼다
분명 어제 커밋한 기록이 있는데
열받지만 업보인 걸 안다
하지만 속상해