-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
65번 문제 질문있습니다
21.02.03 12:56 작성 조회수 99
0
배열 값이 1일때 벽이라고 되어있어서 아래와 같이 7x7배열 상하좌우에 벽을 둘러서 문제를 풀었는데, 만약 배열이 더 커진다면 이런 방식이 시간이나 메모리 부분에서 눈에 띄는 낭비가 발생할까요??
// 65. 미로탐색(DFS)
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> map(9, vector<int>(9,1));
vector<vector<int>> check(9,vector<int>(9));
int goX[]={1,0,-1,0}, goY[]={0,-1,0,1};
int cnt=0;
void dfs(int y, int x){
// printf("%d %d cnt-%d\n",y,x,cnt);
if(x==7&&y==7){
cnt++;
return;
}
for(int i=0;i<4;i++){
if(!map[y+goY[i]][x+goX[i]] && !check[y+goY[i]][x+goX[i]]){
check[y][x]=1;
dfs(y+goY[i],x+goX[i]);
check[y][x]=0;
}
}
}
int main(){
for(int i=1;i<=7;i++)
for(int j=1;j<=7;j++)
cin>>map[i][j];
dfs(1,1);
cout<<cnt;
}
답변을 작성해보세요.
0
답변 1