[leetcode] 815. Bus Routes

문제 링크

LeetCode - The World's Leading Online Programming Learning Platform

 

최소 버스 수를 구하는 문제입니다.

Tip > 문제에 "최소" 라는 말이 있다면, BFS 나 Heap 을 후보군으로 떠올려 봅시다.

 

---

 

Approach : BFS 

 

사용할 샘플 예제는 아래와 같습니다.

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6

 

Algorithm

1. bus 를 저장하기 위해 hashMap adjList 를 초기화합니다.

2. routes 배열을 loop 돌며, 각 bus stop 에 정류하는 bus 들을 adjList 에 저장합니다.

3. BFS 를 구현하기 위해 queue q 를 초기화하고, bus stop 에 중복해서 방문하지 않기 위한 트래킹 용도로 set visit 을 초기화합니다.

4. q 에 초기값으로 source 를 넣고, source 는 방문한 적 있다고 표시하기 위해 visit 에도 source 를 넣어줍니다.

5. q 가 비어있지 않을 때까지 다음 작업을 반복합니다.

   a. q 로부터 bus stop 을 pop 합니다.

   b. 해당 bus stop 이 target 이라면, 정답에 도달한 것이므로 return busCount 해줍니다.

   c. 그렇지 않다면, 해당 bus stop 에 정류하는 bus 들을 loop 돕니다.

       d. 해당 bus 가 정류하는 bus stop 들을 loop 돌며, 방문한 적이 없는 bus stop 이면 q 에 넣어주고 방문 표시 해줍니다.

6. BFS 를 완료했으면, target 에 도달할 수 없다는 뜻이므로 return -1 해줍니다.

 

 

from typing import List
from collections import deque
from collections import defaultdict


class Solution:
    def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
        adjList = defaultdict(set)  # bus stop 에 정류하는 bus 들을 저장

        for i, stops in enumerate(routes):
            for stop in stops:
                adjList[stop].add(i)

        q = deque()  # target 에 도달하기 위한 최소 버스 수를 구하기 위한 큐
        visit = set()  # bus stop 방문 여부 표시

        q.append([source, 0])  # [bus stop, 거쳐온 버스 수]
        visit.add(source)  # source 는 방문했다고 표시

        while q:
            for _ in range(len(q)):
                busStop, busCnt = q.popleft()
                if busStop == target:
                    return busCnt
                for bus in adjList[busStop]:  # 이 bus stop 에 정류하는 bus 들을 탐색
                    for stop in routes[bus]:  # 이 bus 가 거쳐가는 bus stop 들을 탐색
                        if stop not in visit:
                            q.append([stop, busCnt + 1])
                            visit.add(stop)
                    routes[bus] = []
        return -1