WHITECOLLAR 질문드립니다.

  • iyaa
    iyaa

    안녕하세요. WHITECOLLAR를 풀고 있습니다.
    풀이 알고리즘은 다음과 같은데, 뭐가 오류인지 안풀리네요.

    1) 0 -> N-1 으로 가는 경로를 BFS를 통해 찾습니다.
    2) 실제 경로를 구합니다.
    여기서, 실제 경로가 나오지 않는 경우는 100만개짜리 크기의 vector를 반환합니다.
    3) 지금까지 찾은 최소 경로보다 더 짧은 경로를 찾은 경우, 지금까지 체크한 답 (map)을 없애버립니다.
    4) 최소 경로보다 같거나 작은 값을 찾은경우 최소 경로의 크기를 갱신합니다.
    5) 100만개 크기의 vector가 return 된 경우, 무한반복문을 종료하고 답을 출력하는 루틴으로 넘어갑니다.
    6) map를 이용해, 답이 될수 있는값을 map에 체크합니다.
    7) 지금 이용한 간선을 끊어버립니다.

    8) 5)에서 넘어온경우 출력합니다.

    논리적 문제가 있는지, 코딩에 문제가 있는지 잘 모르겠네요 ㅜㅜ

    #define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #include<sstream>
    #include<string>
    #include<vector>
    #include<cmath>
    #include<cstdio>
    #include<cstdlib>
    #include<fstream>
    #include<cassert>
    #include<numeric>
    #include<set>
    #include<map>
    #include<queue>
    #include<list>
    #include<deque>
    #define INF 987654321
    using namespace std;
    void bfs(int src, vector<vector<int> >& graph, vector<int>& parent){
        int N = graph.size();
        vector<int> visit = vector<int>(N, 0);
        parent= vector<int>(N, -1);
        queue<int> q;
        visit[src] = 1;
        parent[src] = src;
        q.push(src);
        while (!q.empty()){
            src = q.front();
            q.pop();
            for (int i = 0; i < N; i++){
                if (graph[src][i] == 1 && !visit[i]){
                    visit[i] = 1;
                    parent[i] = src;
                    q.push(i);
                }
            }
        }
    }
    
    vector<int> solve(int v, const vector<int>& parent){
        vector<int> mang(1000000, 0);
        if (v == -1){ return mang; }
        vector<int> path(1, v);
        while (parent[v] != v){
            v = parent[v];
            if (v == -1){ return mang; }
            path.push_back(v);
        }
        reverse(path.begin(), path.end());
        return path;
    }
    int main(){
        double C;
        cin >> C;
        while (C--){
            int N, M;
            cin >> N >> M;
            vector<vector<int > > graph;
            for (int i = 0; i < N; i++){ 
                vector<int> vbuf;
                for (int j = 0; j < N; j++){
                    vbuf.push_back(0);
                }
                graph.push_back(vbuf);
            }
    
            for (int i = 0; i < M; i++){
                int a, b;
                cin >> a >> b;
                a--; b--;
                graph[a][b] = 1;
            }
            int smallsize = INF;
            map<int, int> lastret;
            while (true){
                vector<int> parent;
                parent.clear();
                bfs(0, graph, parent);
                vector<int> ret = solve(N - 1, parent);
                if (smallsize>ret.size()){
                    lastret.clear();
                }
                if (smallsize >= ret.size()){ smallsize = ret.size(); }
                if (ret.size() == 1000000){ break; }
                for (int i = 0; i < ret.size(); i++){
                    lastret[ret[i]] = 1;
                }
                for (int i = 0; i < ret.size() - 1; i++){
                    int a = ret[i];
                    int b = ret[i + 1];
                    graph[a][b] = 0;
                }
            }
            map<int, int>::iterator it;
            vector<int> finalret;
            for (it = lastret.begin(); it != lastret.end(); it++){
                finalret.push_back(it->first + 1);
            }
            for (int i = 0; i < finalret.size() - 1; i++){
                cout << finalret[i] << " ";
            }
            cout << finalret[finalret.size() - 1] << endl;
    
    
        }
        system("pause");
    }
    

    9년 전
1개의 댓글이 있습니다.
  • iyaa
    iyaa

    자문자답.
    0 1 2 3 4

    0 1
    1 2
    1 3
    2 4
    3 4
    이러한 경우에 0,1이 사라져버리니 0,1,2,4를 찾아버렸으면 0,1,3,4는 못찾겠네요;;


    9년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.