백준 2021 최소 환승 경로 c++,Kotlin (bfs)

문제 출처 : https://www.acmicpc.net/problem/2021

2021번: 최소 환승 경로

문제

어떤 도시의 지하철 노선에 대한 정보가 주어졌을 때, 출발지에서 목적지까지의 최소 환승 경로를 구하는 프로그램을 작성하시오. 실제 경로를 구할 필요는 없고, 환승 회수만을 구하면 된다.

입력

첫째 줄에 역의 개수 N(1≤N≤100,000), 노선의 개수 L(1≤L≤100,000)이 주어진다. 다음 L개의 줄에는 각 노선이 지나는 역이 순서대로 주어지며 각 줄의 마지막에는 -1이 주어진다. 마지막 줄에는 출발지 역의 번호와 목적지 역의 번호가 주어진다. 역 번호는 1부터 N까지의 정수로 표현된다. 각 노선의 길이의 합은 1,000,000을 넘지 않는다.

출력

첫째 줄에 최소 환승 회수를 출력한다. 불가능한 경우에는 -1을 출력한다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

풀이

풀이를 정확하게 설계하지 않으면 디버깅할 때 애를 먹는 문제이다.

해당 문제를 설계함에 있어 가장 중요한 부분은 그래프 설계이다.

 

우선 답을 구하기 위해선, 출발 역을 지나는 호선을 알아야 하고,

해당 호선에 도착 역이 없으면 다른 호선으로 환승을 해야 한다.

이를 위해, 호선이 지나는 역들을 저장한 리스트, 해당 역을 지나는 호선을 저장한 리스트가

필요하단 것까지는 어렵지 않게 생각할 수 있다.

문제에서 같은 호선에 있는 역으로 이동할 때는 가중치가 0이다.

따라서 호선과 호선의 연결을 간선으로 간주하고, 한 호선의 역들을 돌면서 환승할 수 있으면(간선을 만나면)

visited[호선]에 가중치를 갱신하고 해당 호선의 역들을 돌아 도착 역을 찾는다.

 

본인은 호선의 리스트와 역의 리스트를 구분하기 위해 다음과 같은 방법을 사용했다.

-역의 개수가 n일 때, 그래프의 크기를 n*2+1만큼 잡는다.

-graph[호선+n] = {역}, graph[역] = {호선}

 

ex) n=10이고 1호선이 지나는 역이 1,2,3일 때

graph[11] = {1,2,3}

graph[1] = {11}

graph[2] = {11}

graph[3] = {11} 

 

이후 bfs로 그래프를 탐색할 때 인덱스가 n보다 작으면 가중치 0(호선 내에서 역의 이동)

인덱스가 n보다 크면 가중치 +1(다른 호선으로 이동)로 갱신하며, 방문하지 않은 호선들을 방문해가며

도착 역을 찾으면 된다.

코드(c++)

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 200001
using namespace std;

int n, m, start, e;
int visited[MAX];
vector<int> graph[MAX];

int bfs() {
	queue<pair<int, int>> q;
	q.push({ -1, start });

	while (!q.empty()) {
		int cur = q.front().second;
		int dis = q.front().first;
		q.pop();
		for (int i = 0; i < graph[cur].size(); i++) {
			int next = graph[cur][i];
			if (visited[next] > -1)
				continue;
			//호선
			if (next > 100000) {
				q.push({ dis + 1,next });
				visited[next] = dis + 1;
			}
			//도착
			else if (next == e) {
				return dis;
			}
			//역
			else {
				q.push({ dis,next });
				visited[next] = dis;
			}

		}
	}
	return -1;
}

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

	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int num;
		cin >> num;
		while (num != -1) {
			graph[num].push_back(i + 100000);
			graph[i + 100000].push_back(num);
			cin >> num;
		}
	}
	cin >> start >> e;
	fill_n(visited, MAX, -1);

	cout << bfs();

	return 0;
}

코드(Kotlin)

import java.util.*

fun bfs(graph : Array<MutableList<Int>>, visited : IntArray, start : Int, end : Int ,n :Int) : Int {
    val q : Queue<Int> = LinkedList<Int>()
    q.add(start)
    while(q.isNotEmpty()){
        val cur = q.poll()
        for(i in graph[cur].indices){
            val next = graph[cur][i]
            if(visited[next]>=0) continue
            //호선
            if(next>n){
                q.add(next)
                visited[next] = visited[cur]+1
            }
            //도착
            else if(next==end){
                return visited[cur]
            }
            //역
            else{
                q.add(next)
                visited[next]=visited[cur]
            }
        }
    }
    return -1
}

fun main()= with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    var tk = StringTokenizer(br.readLine())
    val (n,m) = List(2){Integer.parseInt(tk.nextToken())}
    val graph = Array(n*2+1,{mutableListOf<Int>()})
    val visited = IntArray(n*2+1,{-1})
    for(i in 1 .. m){
        tk = StringTokenizer(br.readLine())
        var num = Integer.parseInt(tk.nextToken())
        while(num!=-1){
            graph[num].add(n+i)
            graph[n+i].add(num)
            num = Integer.parseInt(tk.nextToken())
        }
    }
    tk = StringTokenizer(br.readLine())
    val (start,end) = List(2){Integer.parseInt(tk.nextToken())}
    write("${bfs(graph,visited,start,end,n)}")
    close()

}