-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
65번 문제 질문이 있습니다.
20.09.22 17:57 작성 조회수 108
0
선생님의 강의를 보기 전, 아래와 같이 스스로 답을 작성해보았습니다. 첫번째 input case의 경우, 답이 1로 나와 오답이 나와버렸는데요, 아래에서 어떤 부분이 잘못됐는지 설명을 듣고싶습니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int arr[10][10], ans = 0, ny = 0, nx = 0;
int my[4] = {1,0,-1,0};
int mx[4] = {0,1,0,-1};
bool check[10][10] = {false,};
bool track(int y, int x){
if(y<1||y>7||x<1||x>7||check[y][x]||arr[y][x]==1) return false;
return true;
}
void dfs(int y, int x){
if(y==7&&x==7){
ans++;
}
else{
for(int i=0; i<4; i++){
ny = y+my[i];
nx = x+mx[i];
if(track(ny,nx)){
check[ny][nx] = true;
dfs(ny,nx);
check[ny][nx] = false;
}
else continue;
}
}
}
int main(void){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
for(int i=1; i<=7; i++){
for(int j=1; j<=7; j++){
cin >> arr[i][j];
}
}
check[1][1] = true;
dfs(1,1);
cout << ans << "\n";
return 0;
}
답변을 작성해보세요.
1
김태원
지식공유자2020.09.24
안녕하세요^^
재귀함수는 자신의 매개변수와 지역변수를 스택프레임에 저장하고 컨트롤합니다. 재귀함수를 사용해 백트랙킹을 하려면 컨트롤 변수들의 재귀함수의 지역변수이어야 합니다. 위 코드에서 변수 ny, nx를 전역으로 잡으면 안되고 dfs 함수의 지역변수로 선언하시면 됩니다.
void dfs(int y, int x){
int ny, nx;
if(y==7&&x==7){
ans++;
}
else{
for(int i=0; i<4; i++){
ny = y+my[i];
nx = x+mx[i];
if(track(ny,nx)){
check[ny][nx] = true;
dfs(ny,nx);
check[ny][nx] = false;
}
else continue;
}
}
}
답변 1