풀어보면 좋은 문제 목록 - 2580 스토쿠 DFS 질문입니다!!

Question

강의 완강하고 선생님께서 주신 추가 문제들 풀어보고 있습니다... https://www.acmicpc.net/problem/2580 2580 스토쿠 문제같은 경우에 강의에서 배워왔던 dfs와 형태가 달라서 고생중입니다 #include #include #include using namespace std; int arr[82][82]; vector > 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

codingcamp · Answer

안녕하세요^^ 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; }

HB · Answer

원본 코드를 첨부합니다 #include #include #include using namespace std; int arr[82][82]; vector > 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; }