[백준 5214] 환승 (파이썬 / Python)

---

📑 문제

문제링크 : 환승

---

🎯 풀이방법

BFS 문제이며, 시간복잡도는 $O(K M)$ 입니다.

arr : 하이퍼튜브 리스트

hyper : 각 역이 존재하는 하이퍼튜브 idx를 담은 리스트

visited : 이미 방문한 역의 번호

que & new_que : BFS를 진행하기 위한 큐

cur : BFS에서 현재 역의 번호

nxt : BFS에서 cur과 같은 하이퍼 튜브에 있으면서 방문한 적 없는 역

ans : 답으로 BFS의 단계

1. 문제의 조건들을 입력받고 초기화 해줍니다.

2. que에 1번 역을 넣고, visited[1] = True로 설정합니다.

3. que에 원소가 있을 동안 계속해서 BFS를 수행합니다. 만약 원소가 없다면 6번으로 갑니다.

4. que에서 원소를 하나씩 꺼내어( = cur ) 현재 역이 N번 역이라면 ans를 return, 아니라면 다음을 수행합니다.

   1. cur이 존재하는 하이퍼튜브에 존재하는 cur이 아닌 역들 중, 아직 방문하지 않은 역들( = nxt )을 new_que에 넣어줍니다.

   2. visited[nxt] = True를 해줍니다.

   3. 이미 이용한 하이퍼튜브들은 다음에 또 사용하면 안되므로, 사용한 하이퍼튜브에는 아무 역이 없도록 초기화시켜줍니다.

5. ans를 하나 늘려주고 que에 new_que를 할당해주며 3번으로 갑니다.

6. N번째 역으로 갈 수 없는 것이므로 -1을 return 해줍니다.

---

🔎 유의할 점

• 각 하이퍼 튜브는 한 번씩만 탐색해주어야 합니다. 그래서 제 코드의 37번 라인에서 arr[h] = [ ] 를 해주어, 31번 라인의 for문을 각 하이퍼튜브가 한 번씩만 돌도록 보장해주었습니다.

---

💻 코드

from sys import stdin

input = stdin.readline


def solve():
    N, K, M = map(int, input().split())
    if N == 1:
        return 1
    arr = [[*map(int, input().split())] for _ in range(M)]

    # hyper[i] = [j] --> j번째 하이퍼튜브에 i번 역이 있다
    hyper = [[] for _ in range(N + 1)]
    for i in range(M):
        for j in arr[i]:
            hyper[j].append(i)

    visited = [False] * (N + 1)
    visited[1] = True

    que, ans = [1], 1
    # bfs
    while que:
        new_que = []
        for _ in range(len(que)):
            cur = que.pop()
            if cur == N:
                return ans
            # cur역이 존재하는 하이퍼 튜브를 돌면서 다음에 갈 수 있는 역을 que에 넣어준다
            for h in hyper[cur]:
                for nxt in arr[h]:
                    if not visited[nxt]:
                        new_que.append(nxt)
                        visited[nxt] = True

                # 하이퍼 튜브는 한 번만 이용되어야 하므로 비워준다
                arr[h] = []

        que = new_que
        ans += 1

    return -1


if __name__ == '__main__':
    print(solve())