[BOJ-5214]환승

음 풀자

문제를 잘못이해했나 제출했는데 틀렸습니다............

다시 풀자

​문제를 잘못이해한거 + 생각도 잘못한거 +

처음에 잘못생각한 것은? 그래프의 구성을 잘못했고,

그래프의 구성을 어떻게 해야하는지? 각 노드와 하이퍼링크는 다른 것이다. 하지만 하이퍼링크에 해당 노드는 다 들어가야한다. 

역n - 하이퍼링크k

역의 갯수가 station

하이퍼링크의 갯수가 hyper_count

이라면 station + hyper_count + 1 를 graph로 구성한다. 

구성된 graph를 방문할 때 하이퍼링크를 방문할 때는 +1 (x), 역을 방문할 때 +1 (o) 한다. 

이와 같은 방법으로 그래프를 BFS 탐색하여... 결과를 출력한다. 

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
 
typedef vector<int> VI;
typedef vector<VI> VVI;
 
struct info{
    int node;
    int count;
    info(int ni, int ci):node(ni), count(ci){}
};
 
VVI G;
VI visited;
int station, hyper, hypercount;
int main(){
    scanf("%d %d %d", &station, &hyper, &hypercount);
    G = VVI(station+1+hypercount,VI(0,0));
    visited = VI(station+1+hypercount,0);
    for(int i = 1 ; i <= hypercount ; i++){
        for(int j = 0 ; j < hyper ; j++){
            int t; scanf("%d", &t);
            G[t].push_back(station+i);
            G[station+i].push_back(t);
        }
    }
 
    queue<info> q;
    q.push(info(1,1));
    visited[1] = true;
    bool impossible = true;
    while(!q.empty()){
        info here = q.front(); q.pop();
        if(here.node == station){
            printf("%d", here.count);
            impossible = false;
            return 0;
        }
        for(auto iter = G[here.node].begin() ; iter != G[here.node].end() ; iter++){
            int tnode = *iter;
            if(!visited[tnode]){
                visited[tnode] = true;
                if(station < tnode && tnode <= station+hypercount) q.push(info(tnode, here.count));
                else q.push(info(tnode, here.count+1));
            }
        }
    }
 
    if(impossible){
        printf("-1");
    }
    
    return 0;
}