글 읽기 - 반례 관련해서 질문드립니다.

aku34587 4년 전 0

다익스트라 알고리즘으로 해결 할 려고 하였는데 어디서 반례가 발생하는지 질문드립니다.

#include <iostream>
#include <climits>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int> > arr;
vector<int> dis;
vector<int> check;

void dfs(int X){
    check[X] = 1;
    for(auto it : arr[X]){
        dis[it] = min(dis[it],dis[X] + 1);
    }
    for(auto it : arr[X]){
        if(check[it] == 0){
            dfs(it);
        }
    }
}

int main(){
    
    vector<int> value;
    int N = 0, M = 0, K = 0, X = 0;
    int vertex = 0, vertex2 = 0;
    int size = 0;
    
    cin >> N >> M >> K >> X;
    
    arr.resize(N);
    dis.resize(N,INT_MAX);
    check.resize(N,0);
    
    dis[X-1] = 0;
    
    for(int i=0;i<M;i++){
        cin >> vertex >> vertex2;
        arr[vertex-1].push_back(vertex2-1);
    }
    
    dfs(X-1);
    
    size = int(dis.size());
    
    for(int i=0;i<size;i++){
        if(dis[i] == K){
            value.push_back(i+1);
        }
    }
    
    if(value.empty()){
        cout << -1 << endl;
    }
    else{
        for(auto it : value){
            cout << it << endl;
        }
    }
    
    return 0;
}

ndb796 4년 전 0

> aku34587

작성하신 소스코드가 다익스트라 알고리즘을 바르게 구현한 소스코드가 맞는지,

또한 본 문제를 다익스트라 알고리즘으로 푸는게 효율적인지에 대해서 조금 더 고민해 보시면 좋을 것 같습니다.

BOJ 2178번 미로 탐색 문제부터 풀어보시는 것을 권장합니다!

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

문제

문제

출처

ICPC

반례 관련해서 질문드립니다.

aku34587 4년 전 0

ndb796 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말