백준 - 최소 환승 경로(2021번) c++

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

2021번: 최소 환승 경로

출발역에서 도착역까지 환승 최소 횟수를 구하는 문제

뭔가 bfs 또는 dfs를 사용하면 뚝딱 풀릴듯 말듯.. 아이디어를 떠오르기가 쉽지 않았다.

결국 답을 구해야 하는것은 환승 최소 횟수이므로 각 역을 기준으로 탐색을 하는 것이 아닌 노선을 기준으로 탐색을 해보기로 했다.

 

입력이 다음과 같을때

10 3
1 2 3 4 5 -1
9 7 10 -1
7 6 3 8 -1
1 10

사용할 변수들은 다음과 같다.

route : 각 노선이 어떤 역을 지나가는지 저장

route[1] = {1, 2, 3, 4, 5}

route[2] = {9, 7, 10}

route[1] = {7, 6, 3, 8}

 

nodes : 각 역이 몇번 노선에 위치해 있는지 저장

node[1] = {1}

node[2] = {1}

node[3] = {1, 3}

node[4] = {1}

node[5] = {1}

node[6] = {3}

node[7] = {2, 3}

node[8] = {3}

node[9] = {2}

node[10] = {2}

 

visited : 노선의 방문 여부를 저장

 

주요 알고리즘은 다음과 같다.

  queue<pair<int, int>> Q;
  for (auto a : nodes[st]) {
    Q.push({a, 0});
    visited[a] = true;
  }
  while (!Q.empty()) {
    auto cur = Q.front();
    Q.pop();
    for (auto a : route[cur.first]) {
      if (a == ed) {
        ans = min(ans, cur.second);
        break;
      } else {
        for (auto node : nodes[a]) {
          if (visited[node])
            continue;
          visited[node] = true;
          Q.push({node, cur.second + 1});
        }
      }
    }
  }
  if (ans == INT_MAX)
    ans = -1;

Q pair의 첫 번째 원소는 현재 방문 중인 노선, 두 번째 원소는 현재까지 환승 횟수이다.

현재 방문 중인 노선도에 도착역이 포함되어 있으면 최솟값을 답으로 바꿔주고

도착역이 포함되어 있지 않다면 환승 할 수 있는 노선으로 환승해주고 환승 횟수를 +1 해준다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int n, l;
vector<int> route[100001];
vector<int> nodes[100001];
bool visited[100001];
int main(void) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin >> n >> l;
  int t;
  for (int i = 1; i <= l; i++) {
    vector<int> tmp;
    while (true) {
      cin >> t;
      if (t == -1)
        break;
      route[i].push_back(t);
      nodes[t].push_back(i);
    }
  }
  int st, ed;
  cin >> st >> ed;
  int ans = INT_MAX;
  // 현재 노선, 환승 횟수
  queue<pair<int, int>> Q;
  for (auto a : nodes[st]) {
    Q.push({a, 0});
    visited[a] = true;
  }
  while (!Q.empty()) {
    auto cur = Q.front();
    Q.pop();
    for (auto a : route[cur.first]) {
      if (a == ed) {
        ans = min(ans, cur.second);
        break;
      } else {
        for (auto node : nodes[a]) {
          if (visited[node])
            continue;
          visited[node] = true;
          Q.push({node, cur.second + 1});
        }
      }
    }
  }
  if (ans == INT_MAX)
    ans = -1;
  cout << ans;
  return 0;
}