글 읽기 - C++반례가 뭐가 있나요 ㅜㅜ

jw_ryux 4년 전 0

범위값 이상도 없는 것 같은데 뭐때문에 계속 틀린건지 모르겠어요 ㅜㅜ

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

bool visit[100001];

int n, k;
int d[3] = {-1, 1, 2};

int bfs(int me, int mov){
    queue<pair<int, int> > q;
    visit[me] = true;
    q.push(make_pair(me, mov));
 
    while(!q.empty()){
        int c = q.front().first;
        int sec = q.front().second;

        if(c == k){
            break;
        }

        q.pop();

        for(int i = 0; i < 3; i++){ //세가지 경우
            int nc; //다음 점
            if(i == 2) {
                nc = c * d[i]; // 현재 점 * 2
                if(0<= nc && nc<= 100000){
                    if(!visit[nc]){
                        visit[nc] = true;
                        q.push(make_pair(nc, sec));
                    }
                }
            } 
            else{
                nc = c + d[i]; //현재점 +- 1
                if(0<= nc && nc<= 100000){
                    if(!visit[nc]){
                        visit[nc] = true;
                        q.push(make_pair(nc, sec+1));
                    }
                }
            } 

        }
    }
    return q.front().second;
}

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin >> n >> k;

    int ans = bfs(n, 0);
    cout << ans << "\n";
    return 0;
}

jw_ryux 4년 전 1

순간이동은 0초가 걸리기때문에 순간이동을 먼저 큐에 넣어야했네요. 그래서 D[3] 배열을 {2, 1, -1} 로 바꾸고 첫번째로 계산되도록 했습니다. 이런 실수하시는 분 있으실 거 같아서 남겨놓을게요!!

이 문제에서는 간선의 특성 때문에 그렇게 해도 통과되지만, 보다 일반적인 그래프에서는 그렇게 하면 안 됩니다. BFS라는 것 자체가 간선의 가중치가 서로 같을 때만 사용할 수 있는 것이고, 서로 다르면 다익스트라를 사용해야 합니다. 순간이동을 10000번 사용한 것이 +1을 한 번 한 것보다 더 거리가 가까운 것인데, 실제로 큐에서 나오는 시간은 매우 매우 매우 나중입니다.

jw_ryux 4년 전 0

아 그렇네요 dfs/bfs 관련 문제만 풀다보니 가중치가 다른 걸 생각못했네요 정말 감사합니다!

huozuyinshua 2년 전 0

djm03178 감사합니다.

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

문제

문제

출처

ICPC

C++반례가 뭐가 있나요 ㅜㅜ

jw_ryux 4년 전 0

jw_ryux 4년 전 1

djm03178 4년 전 2

jw_ryux 4년 전 0

huozuyinshua 2년 전 0

djm03178 감사합니다.

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말