인프런 커뮤니티 질문&답변

배열 값이 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;
}