[LeetCode] - 815. Bus Routes

https://leetcode.com/problems/bus-routes/description/

Bus Routes - LeetCode

leetcode - Bus Routes

문제 유형 : 최단 거리 / 그래프

문제 난이도 : Hard

 

문제

You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats forever.

• For example, if routes[0] = [1, 5, 7], this means that the 0th bus travels in the sequence 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... forever.

You will start at the bus stop source (You are not on any bus initially), and you want to go to the bus stop target. You can travel between bus stops by buses only.

Return the least number of buses you must take to travel from source to target. Return -1 if it is not possible.

 

당신은 버스 노선을 받습니다.

route[i] = [1, 5, 7]이라면, 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> ... 로 이동합니다

당신은 버스 정류장 source에서 시작합니다.(당신은 어느 버스에 탄 상태가 아닙니다.)

당신은 target까지 가야 합니다.

도착하기 위한 최소의 버스 수를 구하시오. 도달할 수 없느면 -1을 반환하시오.

 

 

풀이

90%정도 풀었는데, 일부 테스트케이스에서 통과하지 못해서

아래 솔루션의 도움을 받았습니다..

https://leetcode.com/problems/bus-routes/solutions/4277851/beats-100-00-of-users-with-python-and-beats-100-00-of-users-with-python/

🚀Beats 100.00%of users with Python and ✅Beats 100.00%of users with Python - undefined - LeetCode

각 노드(정류장)에서 탈 수 있는 노선을 담는다.

 

 

그리고 BFS를 이용하여 순회하는데, {정류장 번호, 지금까지의 버스 탄 횟수}로 저장한다.

현재 정류장에서 갈 수 있는 노선들의 각 정류장들 중에서, 아직 방문하지 않으면 큐에 넣는다.

탐색 중에서 target을 발견하면 멈추고, 다 순회하고 나서도 도달하지 못하면 -1을 반환한다.

 

 

코드

C++

class Solution {
public:
    int numBusesToDestination(std::vector<std::vector<int>>& routes, int source, int target) {
        if (source == target) {
            return 0;
        }
		
        // 지금 노드에서 갈 수 있는 버스노선들 저장
        unordered_map<int, unordered_set<int>> stopToRoutes;
        for (int i = 0; i < routes.size(); ++i) {
            for (int stop : routes[i]) {
                stopToRoutes[stop].insert(i);
            }
        }
		
        // 방문 정보 저장...
        unordered_set<int> visitedStops;
        queue<pair<int, int>> queue;  // {bus stop, number of buses taken}
		
        // source, 0개의 버스탑승 횟수부터 시작
        queue.push({source, 0});

        while (!queue.empty()) {
            auto currentStopAndBuses = queue.front();
            queue.pop();
            int curr = currentStopAndBuses.first;
            int busCount = currentStopAndBuses.second;

			// 지금 정류장에서 갈 수 있는 노선 불러오기
            const auto& routesForCurrent = stopToRoutes[curr];
            for (int routeIdx : routesForCurrent) {
                for (int nextStop : routes[routeIdx]) {
                    if (nextStop == target) {
                        return busCount + 1;
                    }

					// 만약 간적 없는 정류장이라면 큐에 추가
                    if (visitedStops.find(nextStop) == visitedStops.end()) {
                        visitedStops.insert(nextStop);
                        queue.push({nextStop, busCount + 1});
                    }
                }
				
                // 이미 다 체크한 노선이므로 삭제
                routes[routeIdx].clear();
            }
        }

        return -1;
    }
};