백준 2644 촌수계산 - bfs에서 메모리초과가 안뜨게 하려면?

문제 링크

www.acmicpc.net/problem/2644

풀이 아이디어

최단거리 문제니까 당연히 dfs가 아닌 bfs를 이용해서 푸는 것이다.

노드번호와 cost의 쌍을 큐에 넣고 bfs돌리면 쉽게 풀 수 있다.

문제는 메모리!

아래 주석 친 부분에 처음에 if-return문을 넣었다가 메모리 초과가 떴었다.

BFS 조건 판단은 반드시 방문여부 체크한 후에 하기!!

코드

#include <bits/stdc++.h>
using namespace std;

vector<int> tree[101];
bool visited[101];

int bfs(int a, int b){
    queue<pair<int,int>> q;
    q.push({a,0});
    visited[a]=true;
    while(!q.empty()){
        int front = q.front().first;
        int cost = q.front().second;
        q.pop();
        for(int i=0; i<tree[front].size(); i++){
        	// if문이 여기 들어가는 순간 메모리 초과가 뜨는거다.
        	// if(tree[front][i]==b){
            //        return cost+1;
            //    }
            if(!visited[tree[front][i]]){
                visited[tree[front][i]]=true;
                if(tree[front][i]==b){
                    return cost+1;
                }
                q.push({tree[front][i],cost+1});
            }
        }
    }
    return -1;
}

int main(void){
    int n,s,e,m,a,b;
    cin>>n>>s>>e>>m;
    for(int i=0; i<m; i++){
        cin>>a>>b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    cout<<bfs(s,e);
    return 0;

}