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

항상 꼼꼼한 답변 감사드립니다. 선생님 덕분에 해결 되었습니다 :)

안녕하세요 ㅎㅎ

BFS라고 해서 성능차이가 큰게 아닙니다. 제가 flag, visited 부분만 제외하고 비슷하게 짜봤는데 8ms 정도가 나옵니다.

#include<bits/stdc++.h>
using namespace std;
int n,m, x1, w1, x2, y2, y, x;
char a[301][301];
int visited[301][301];
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};

int main() {
    cin >> n >> m;
    cin >> w1 >> x1 >> y2 >> x2; 
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            cin >> a[i][j];
        }
    }
    visited[w1][x1] = 1;
    queue<pair<int,int>> q;
    q.push({w1, x1});
    int cnt = 0;
    while(a[y2][x2]!='0') {
        cnt++;
        queue<pair<int, int>> p;
        while(q.size()) {
            tie(y,x) = q.front(); q.pop();
            for(int i=0; i<4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                if(ny<1||nx<1||ny>n||nx>m) continue;
                if(visited[ny][nx]) continue;
                visited[ny][nx] = cnt;
                if(a[ny][nx]!='0') {
                    a[ny][nx] = '0';
                    p.push({ny,nx});   
                }
                else q.push({ny,nx});
            }
        }
        q = p;
    }
    cout << visited[y2][x2]; 
}

0일 때 visited 를 안거셔서 -> 0 인 부분이 반복적으로 탐색했기 때문에 이부분이 많이 걸리는 것 같습니다.

dfs의 재귀 호출 깊이가 최대를 초과하여 스택 오버플로우가 발생

-> 네 간혹 불필요하게 많이 호출되면 스택 오버플로우가 발생합니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.