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

큰돌님 안녕하십니까?

해당 문제 2636 치즈 문제가 떠올라서 DFS로 풀이를 해서 통과했는데요, 해설에는 BFS 하셔서 질문 올립니다.

해당 문제 DFS풀이는 어떻다고 생각하시나요?

왜냐하면 이 다음 문제인 3-K 3197 백조의 호수는 이래 풀면 시간 초과 뜨더라구요!

제가 짠 코드는 2636 치즈 참고해서 아래와 같습니다.

http://boj.kr/cc3ec76201724d44a5c35f955a9e41cc

#include <bits/stdc++.h>

using namespace std;

////////////bfs dfs 용//////////

char a[302][302];

int visited[302][302];

int m,n;

int aa,bb;

int c,d;

string oneline;

const int dy[] = {-1, 0, 1, 0};

const int dx[] = {0, 1, 0, -1};

vector<pair<int,int>> temp;

int ret;

bool dfs(int y, int x)

{

bool tempbool=false;

visited[y][x]=1;

for(int i = 0; i< 4;i++)

{

int ny = y + dy[i];

int nx = x + dx[i];

if( ny<0|| ny>=m || nx < 0 ||nx>=n) continue;

if(visited[ny][nx]==1) continue;

if(a[ny][nx]=='#')

{

return true;

}

if(a[ny][nx]== '1')

{

temp.push_back({ny,nx});

continue;

}

else

{

tempbool = dfs(ny,nx);

if(tempbool) return tempbool;

}

}

return tempbool;

}

int main(){

ios_base::sync_with_stdio(false);

cin.tie(NULL);

cin>>m>>n;

cin>>aa>>bb>>c>>d;

for(int i = 0 ; i< m ; i++)

{

cin>>oneline;

for(int j=0; j<n;j++)

{

a[i][j]= oneline[j];

}

}

while(true)

{

ret++;

fill(&visited[0][0], &visited[0][0]+302*302,0);

bool tempbool= dfs(aa-1,bb-1);

if(tempbool) break;

while(temp.size())

{

pair<int,int> aaa = temp[temp.size()-1];

temp.pop_back();

a[aaa.first][aaa.second] = '0' ;

}

}

cout<<ret;

return 0;

}

답변 미리 감사합니다.