[BOJ] 2580 스도쿠

 

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

2580번: 스도쿠

 

스도쿠 배열을 입력받는 중 입력값이 0인 좌표를 vector v에 저장하고 입력이 종료된 후

v에있는 좌표를 뽑아 1~9의 값을 각각 넣어보며 입력가능한 값을 미리 arr[9][9]배열에 저장해 놓았습니다.

이후 vector v 의 인덱스 순서대로 가능한 값을 넣어가며 백트래킹으로 문제를 풀 수 있었습니다.

 

#include<iostream>
#include<vector>
#pragma warning (disable:4996)
using namespace std;
// 2580 스도쿠
vector<int> arr[9][9];
vector<pair<int, int>>v;
int pan[9][9];
bool avail(int i,int j) {
	int num = pan[i][j];
	int ii = (i / 3)*3;
	int jj = (j / 3) * 3;
	int cnt = 0;
	for (int iii = 0; iii < 9; iii++) {
		if (num == pan[iii][j])
			cnt++;
	}
	if (cnt > 1)
		return false;
	for (int jjj = 0; jjj < 9; jjj++) {
		if (num == pan[i][jjj])
			cnt++;
	}
	if (cnt > 2)
		return false;
	for (int iii = ii; iii < ii + 3;iii++) {
		for (int jjj = jj; jjj < jj + 3;jjj++) {
			if (pan[iii][jjj] == num)
				cnt++;
		}
	}
	return cnt == 3;
}
void print() {
	for (int i = 0; i < 9;i++) {
		for (int j = 0; j < 9;j++) {
			cout << pan[i][j]<<" ";
		}
		cout << endl;
	}
}
bool solve(int n) {
	if (n == v.size()) {
		print();
		return true;
	}
	int i = v[n].first, j = v[n].second;
	for (int k = 0; k < arr[i][j].size(); k++) {
		pan[i][j] = arr[i][j][k];
		if(avail(i,j))
			if (solve(n + 1))
				return true;
	}
	pan[i][j] = 0;
	return false;
}
int main(){
	for (int i = 0; i < 9;i++) {
		for (int j = 0; j < 9;j++) {
			cin >> pan[i][j];
			if (pan[i][j] == 0) {
				v.push_back({ i,j });
			}
		}
	}
	for (int n = 0; n < v.size();n++) {
		int i = v[n].first,j=v[n].second;
		for (int m = 1; m <= 9;m++) {
			pan[i][j] = m;
			if (avail(i, j)) 
				arr[i][j].push_back(m);
		}
		pan[i][j] = 0;
	}

	if (solve(0)) {
		return 0;
	}
	else
		cout << -1;
}

 

 

#잡설

풀이도중 두번정도 런타임 에러가 발생하였습니다..

왜 그런지 한참을 찾다가 77번 라인에서 return 0가 아니라 return true 로 해놨더라구요 ㅋㅋ

return 0로 바꾸니 바로 통과 되었습니다!