백준 5214 환승

www.acmicpc.net/problem/5214

5214번: 환승

신선한 발상, 새로운 시각이 필요한 문제이다. 그 아이디어가 떠오르면 다음은 일반적인 다익스트라 또는 BFS문제가 된다. 하지만 아이디어가 떠오르지 않으면 풀기 어려울 수 있다. 

가끔 퀴즈문제들을 해결하는 기발한 아이디어를 보면, 문제상에는 존재하지 않는 무언가를 더 그려 넣어서, (또는 집어넣어서) 해결하는 경우들이 있다. 또는 뭔가 문제상에서 정확하게 제한을 두진 않았지만, 우리가 은연중에 스스로를 제한하여 해결책을 생각하지 못하는 경우가 있다. 이번 문제도 그런 방식의 발상이 필요하다. 

 

아래의 그림들을 살펴보자.

그래프 문제들을 몇 개 풀어봤다면, 단순하게 위와 같은 그림을 그려볼 수 있다. 1-2-3은 하이퍼 튜브로 연결되어 있으므로, 1-2-3 사이를 이동할 때는 비용이 들지 않는다고 처리할 수 있다. 하지만 3에서 6으로 갈 때는 어떻게 할 것인가? 3은 1-2와 하이퍼 튜브로 연결되어 있지만, 3-6-7도 하이퍼 튜브이다. 그럼 그때 이전에 있었던 정류장이 A하이퍼 튜브이고 그다음이 B하이퍼 튜브이면 비용 발생한 것으로 처리해야 할까? 이런식으로 한다면 하이퍼 튜브를 모두 집합이나 맵에 묶어줘야 하고, 매번 검색 연산을 해야 하므로 효율적이지 못하다.

 

이 그림은 간선 없이 뭔가 클라우드 형태로 묶어준 것 같지만, 그저 추상적인 그림일 뿐이고, 결국 또 집합 내 검색 연산이 수반된다.

 

이 그림은 하이퍼 튜브로 연결되는 역끼리 직접 연결하지 않고 일종의 '환승역'을 도입하였다. 예를 들어 빨강색 환승역은 3,6,7을 연결하여 주는 것이다. 이렇게 하면 '환승역을 지날 때는 비용이 들지 않는다'라는 처리만 해주면 끝이다. 너무나도 단순해졌다. 환승역을 불러줄 번호를 붙여주고 위의 그림처럼 그래프를 다시 그려주면 되는 것이다. 간선의 비용은 따로 있지 않으므로, 사실 BFS만으로도 해결 가능하며, 원한다면 다익스트라를 사용해서 풀 수도 있다.

 

필자는 첫 번째 하이퍼 튜브 환승역을 n+1이라고 칭하고, 이후 환승역 정보가 들어올 때마다 ++해주어서 계속 생성해주었다.

 

<주요 내용>

BFS, 최단 경로, 다익스트라, 더미노드

 

<코드>

아래의 코드는 다익스트라를 사용한 코드이다. BFS로 해결할 수 도 있다.

#include <iostream>
#include <queue>
#include <vector>
#define endl '\n'
using namespace std;
const int sz=1e5+1e3+1,big=1e5+1;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
vector<int>graph[sz];
int a,n,k,m,cost[sz],ht;
bool visited[sz];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cin>>n>>k>>m;
    fill(cost,cost+n+m+1,big);
    ht=n+1;
    while(m--){
        for(int i=0;i<k;++i){
            cin>>a;
            graph[ht].push_back(a);
            graph[a].push_back(ht);
        }
        ht++;
    }
    pq.emplace(1,1);
    cost[1]=1;
    while(!pq.empty()){
        auto curr=pq.top();
        pq.pop();
        if(visited[curr.second])continue;
        visited[curr.second]=1;
        for(auto nx:graph[curr.second]){
            if(nx<=n){
                if(cost[nx]>curr.first+1){
                    cost[nx]=curr.first+1;
                    pq.emplace(curr.first+1,nx);
                }
            }else{
                if(cost[nx]>curr.first){
                    cost[nx]=curr.first;
                    pq.emplace(curr.first,nx);
                }
            }
        }
    }
    if(cost[n]==big)cout<<-1<<endl;
    else cout<<cost[n]<<endl;
    return 0;
}