인프런 커뮤니티 질문&답변
작성한 질문수
풀어보면 좋은 문제 목록 - 2580 스토쿠 DFS 질문입니다!!
작성
·
319
0
강의 완강하고 선생님께서 주신 추가 문제들 풀어보고 있습니다...
https://www.acmicpc.net/problem/2580
2580 스토쿠 문제같은 경우에 강의에서 배워왔던 dfs와 형태가 달라서 고생중입니다
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int arr[82][82];
vector<pair<int, int> > v; //0위치
bool isRight(int n) { //조건 확인***
.... (생략)
}
void dfs(int n) {
if (n==(int)v.size()) {
//결과 출력
....(생략)
exit(0);
return;
}
else {
//선택
for (int i = 1; i <= 9; i++) {
arr[v[n].first][v[n].second] = i; //값 넣기
if (isRight(n)) { //백트래킹 조건 확인***
dfs(n + 1); //계속 진행
}
//else { //취소***??????
// arr[v[n].first][v[n].second] = 0;
//}
}
arr[v[n].first][v[n].second] = 0;
}
}
int main() {
for (int i = 1; i <= 9; i++) {
for (int j = 1; j <= 9; j++) {
int tmp;
cin >> tmp;
if (tmp == 0) v.push_back(make_pair(i,j));
arr[i][j] = tmp;
}
}
dfs(0);
return 0;
}
제 코드가 이러한데 (필요없는 부분은 생략했습니다)
dfs 재귀함수의 경우
v 벡터에 0인 곳의 좌표를 받고, dfs로 해당 좌표에 1부터 9까지 넣어보면서 선택하는 구조입니다.
근데...
재귀 전개하는 부분에서
arr[v[n].first][v[n].second] = 0;
주석에서도 나와있듯이 초기화 하는 부분이 for문 밖으로 빠져나와 있어야 정답으로 인정이 되더라구요
이해가 가지 않아서 질문을 드립니다
제 머리로는 위 부분이 for문 안쪽에 있는 것이랑
for문 바깥쪽에 있는것이랑 무슨 차이가 있는 것인지 전혀 모르겠습니다.
문제를 찾아낸 반례도 첨부합니다
for문 안쪽에 arr[v[n].first][v[n].second] = 0; 가 있을 시
이 케이스에서 0을 숫자로 하나도 채우지 못하고 그대로 결과가 나옵니다
for문 안쪽에 아래 구문이 있는 경우
arr[v[n].first][v[n].second] = 0;왜 못 채우고 다 0으로 빠져나오는 건가요?
TEST CASE # 2
0 2 0 9 0 5 0 0 0
5 9 0 0 3 0 2 0 0
7 0 0 6 0 2 0 0 5
0 0 9 3 5 0 4 6 0
0 5 4 0 0 0 7 8 0
0 8 3 0 2 7 5 0 0
8 0 0 2 0 9 0 0 4
0 0 5 0 4 0 0 2 6
0 0 0 5 0 3 0 7 0
답변 2
1
김태원
지식공유자
안녕하세요^^
else 빼고 해보세요.
for (int i = 1; i <= 9; i++) {
arr[v[n].first][v[n].second] = i; //값 넣기
if (isRight(n)) { //백트래킹 조건 확인***
dfs(n + 1); //계속 진행
}
arr[v[n].first][v[n].second] = 0;
}0
HB
질문자
원본 코드를 첨부합니다
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int arr[82][82];
vector<pair<int, int> > v; //0위치
int d[] = {0,1,1,1,4,4,4,7,7,7}; //사각형
bool isRight(int n) { //조건 확인***
int cnt = 0;
int target = arr[v[n].first][v[n].second];
//[1] 네모칸 하나 중복 확인
int startr = d[v[n].first];
int startc = d[v[n].second];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (target == arr[startr +i][startc +j]) cnt++;
if (cnt == 2) return false;
}
}
//[2] 가로 한줄 중복 확인
cnt = 0;
for (int i = 1; i <= 9; i++) {
if ( target == arr[v[n].first][i] ) cnt++;
if (cnt == 2) return false;
}
//[3] 세로 한줄 중복 확인
cnt = 0;
for (int i = 1; i <= 9; i++) {
if (target == arr[i][v[n].second]) cnt++;
if (cnt == 2) return false;
}
return true;
}
void re(int n) {
if (n==(int)v.size()) {
//결과 출력
for (int i = 1; i <= 9; i++) {
for (int j = 1; j <= 9; j++) {
cout << arr[i][j] << " ";
}
cout << endl;
}
exit(0);
return;
}
else {
//선택
for (int i = 1; i <= 9; i++) {
arr[v[n].first][v[n].second] = i; //값 넣기
if (isRight(n)) { //백트래킹 조건 확인***
re(n + 1); //계속 진행
}
//else { //취소***
// arr[v[n].first][v[n].second] = 0;
//}
}
arr[v[n].first][v[n].second] = 0;
}
}
int main() {
for (int i = 1; i <= 9; i++) {
for (int j = 1; j <= 9; j++) {
int tmp;
cin >> tmp;
if (tmp == 0) v.push_back(make_pair(i,j));
arr[i][j] = tmp;
}
}
re(0);
//결과 출력
for (int i = 1; i <= 9; i++) {
for (int j = 1; j <= 9; j++) {
cout << arr[i][j] << " ";
}
cout << endl;
}
return 0;
}