(C++) - 백준(BOJ) 5214번 : 환승

https://www.acmicpc.net/problem/5214

5214번: 환승

 

bfs 문제였습니다.

 

📕 풀이방법

같은 호선에 속해있는 역끼리는 간선으로 연결할 필요가 없습니다. 유의미한 간선은 역 <-> 호선 또는 호선 <-> 역 뿐입니다. 인접그래프를 형성할 때 정점을 역, 하이퍼튜브로 생각하며 역과 하이퍼튜브 사이를 간선으로 해 형성해줍니다.

 

📔 입력 및 초기화

m개의 호선에 대해 각 호선에 속한 정점들을 k개씩 입력하고 무방향 인접리스트를 형성해줍니다. 하이퍼튜브는 i번 호선 입력시 i에 10만을 더해 다른 정점 혹은 하이퍼튜브와 겹치는 수가 발생하지 않도록 주의합니다.

 

📔 풀이과정

1번 정점을 시작점으로 하는 bfs를 수행합니다.

 1. 1번 정점을 방문했으므로 dist[1] = 1입니다. 그 후 시작점 1을 queue에 push해줍니다.

 

 2. x정점이 n이라면 도착했으므로 dist[x]를 반환해줍니다.

 

 3. x정점에서 인접 정점(next)들 중 처음 방문했을 때 환승역(하이퍼튜브)라면 dist[next] = dist[x] + 1입니다.

    다음 정점이 일반 정점이라면 최소거리가 아니기 때문에 dist[next] = dist[x]입니다. 같은 호선에 속한 역끼리는 이동하면 손해이기 때문에 가중치가 없다고 생각해야 합니다.

 

 4. 모든 정점을 확인했음에도 도착하지 못했다면 -1을 반환합니다.

📔 정답출력

 bfs함수의 반환값을 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int n,m,k,dist[200001];
vector <int> graph[200001];
int bfs(){
    queue <int> q;
    q.push(1);
    dist[1] = 1;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        if(x == n) return dist[x];
        for(auto next : graph[x]){
            if(dist[next]) continue;
            if(next > 100000) dist[next] = dist[x] + 1;
            else dist[next] = dist[x];
            q.push(next);
        }
    }
    return -1;
}

int main(){
    cin >> n >> k >> m;
    for(int i = 1; i <= m; i++){
        for(int j = 0,v; j < k; j++){
            cin >> v;
            graph[v].push_back(i + 100000);
            graph[i + 100000].push_back(v);
        }
    }
    cout << bfs();
}