글 읽기 - bfs 관련된 문제 질문입니다.

vjerksen 7년 전 0

숨바꼭질이라는 bfs문제를 풀다가 ver2가 있어서 문제를 해결하려했습니다.

우선 bfs를 돌면서

배열[현재노드] = 배열[다음노드] +1;

이런식으로 더해가다가 최초에 원하는 목적지점에 도착하면 '배열[현재노드]' 를 저장하고 그 보다 같거나 작은 값만 저장하게했습니다.

왜냐면 제 생각엔 최초에 원하는 목점지점과 같은 높이(?)에 있는 노드들의 배열 값까지만 최소값이라고 생각했기 때문입니다.

test case는 답이 나오는데 무엇이 문제인지 모르겠습니다. 도움 부탁드립니다.

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
#include<string>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<cmath>
#include<climits>
#include<map>
using namespace std;

int N,K;
int timee[100001];
bool visit[100001];
int ans = 1 << 29;
int sum=0;


bool check(int cur){
    if(ans >= cur){
        ans = cur;
        sum++;
        return false;
    }
    else return true;
}
void bfs(){
    queue<int> q;
    q.push(N);
    visit[N] = true;
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        if(!visit[cur+1] && cur+1 >=0 && cur+1 <= 100000){
            if(cur + 1 == K){
                if(check(timee[cur]+1)) break;
            }
            else{
                visit[cur+1] = true;
                q.push(cur+1);
                timee[cur+1] = timee[cur]+1;
            }
        }
        if(!visit[cur-1] && cur-1 >=0 && cur-1 <= 100000){
            if(cur - 1 == K){
                if(check(timee[cur]+1)) break;
            }
            else{
                visit[cur-1] = true;
                q.push(cur-1);
                timee[cur-1] = timee[cur]+1;
            }
        }
        if(!visit[cur*2] && cur*2 >=0 && cur*2 <= 100000){
            if(cur *2 == K){
                if(check(timee[cur]+1)) break;
            }
            else{
                visit[cur*2] = true;
                q.push(cur*2);
                timee[cur*2] = timee[cur]+1;
            }
        }
    }
}
int main(){
    cin >> N >> K;
    bfs();
    printf("%d\n%d",ans,sum);
    return 0;
}

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

문제

문제

출처

ICPC

bfs 관련된 문제 질문입니다.

vjerksen 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말