글 읽기 - BFS 메모리초과

denfor123 3년 전 0

BFS로 풀이했는데 어떤 부분이 문제가 되는지 모르겠습니다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
using namespace std;

int N,K;
set<int> visited;
queue<pair<int, int>> q;

int BFS(int pos, int cnt){
    q.push(make_pair(pos, cnt));
    int p,c;
    while(!q.empty()){
        p=q.front().first;
        c=q.front().second;
        q.pop();
        
        if(visited.find(p)==visited.end()){
            visited.insert(p);
            if(p==K) return c;

            if(visited.find(p*2)==visited.end())
                q.push(make_pair(p*2, c+1));
            if(visited.find(p+1)==visited.end())
                q.push(make_pair(p+1, c+1));
            if(visited.find(p-1)==visited.end())
                q.push(make_pair(p-1, c+1));
        }
    }
}

int main(){
    scanf("%d%d", &N, &K);
    printf("%d", BFS(N, 0));
}

djm03178 3년 전 1

BFS는 큐에서 뺀 뒤가 아니라 큐에 넣을 때 방문 표시를 해야 중복 방문이 일어나지 않습니다.

denfor123 3년 전 0

감사합니다. djm03178님 덕분에 해결했습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

BFS 메모리초과

denfor123 3년 전 0

djm03178 3년 전 1

denfor123 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말