https://www.acmicpc.net/problem/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로 바꾸니 바로 통과 되었습니다!
'개발 > 알고리즘' 카테고리의 다른 글
2020 카카오 인턴십 코딩테스트 후기 (0) | 2020.05.10 |
---|---|
2020 Dev-Matching: 웹 백엔드 코딩테스트 후기 (3) | 2020.04.28 |
[BOJ] 17071 숨박꼭질5 (0) | 2020.04.04 |
[BOJ] 9935 문자열 폭발 (0) | 2020.03.29 |