[알고리즘/백준] 2021번 최소 환승 Python 파이썬

 

이번 문제는 오랜만에 스스로의 힘으로 풀어볼 수 있었던 문제입니다.

 

골드 2를 스스로 풀다니 실력이 늘고 있는 건가..!!!

 

노선별로 지나는 역들이 주어졌을 때 출발역과 도착역이 주어지고 최소 환승 회수를 구하는 문제입니다. 보고 탐색해야하는 문제이니 BFS 로 풀어야겠다고 생각하였습니다. 해당 문제를 쉽게 풀기 위해서 먼저 저장할 때 각 역별로 지나는 노선 번호, 노선별로 지날 수 있는 역 번호들로 리스트를 만들어 저장하였습니다.

 

그 다음 풀이한 로직을 설명하자면, 시작점이 주어졌을 때

1. 해당 역에서 지나는 노선을 확인한다.

2. 이미 탄 노선인지 아닌지 확인한다.

3. 만약 안 탄 노선이라면 해당 노선에서 갈 수 있는 역을 확인한다

4. 갈 수 있는 역에서 도착역이 있는 확인한다.

5. 도착역이 있다면, 이때까지 누적된 환승 회수를 비교해준다.

4. 도착역이 없고, 갈 수 있는 역이 이미 들린 곳이 아니라면 옮겨서 타본다. 

이렇게 처리를 해준다면 이미 탄 노선이나 들린 역을 들리지 않고 검사를 진행할 수 있습니다. 

 

참고 이미지

 

다만, 해당 문제는 지나는 모든 역을 검사해줘야하며 최소값을 구해야하기 때문에 도착지에 도착했을 때 누적된 환승 횟수를 비교하여 적은 값을 저장해줘야합니다. (예를 들어 2번만에 도착할 수 있는 방법도 있고 5번만에 도착할 수 있는 방법도 있을 수 있으니) 또한, 도착할 수 없을 경우(-1)와 시작역과 도착역이 같은 경우(0)도 예외처리해주었습니다. 

 

다음과 같은 코드로 통과하였습니다.

 

import sys
from collections import deque
input = sys.stdin.readline

n, l = map(int, input().split())
station = [[] for _ in range(n+1)]
l_list = [[] for _ in range(l+1)]

for i in range(1, l+1):
    l_l = list(map(int, input().split()))
    for j in range(len(l_l)-1):
        station[l_l[j]].append(i)
        l_list[i].append(l_l[j])

station_visited = [False] * (n+1)
l_visited = [False] * (l+1)
start, end = map(int, input().split())

def bfs():
    queue = deque([])
    queue.append((0,start))
    answer = 1000000
    station_visited[start] = True
    while queue:
        n, s = queue.popleft()
        s_list = station[s] # 연결된 노선
        for i in range(len(s_list)): # 연결된 노선
            if l_visited[s_list[i]] == False:
                l_visited[s_list[i]] = True
                for j in range(len(l_list[s_list[i]])): # 갈 수 있는 역
                    if l_list[s_list[i]][j] == end:
                        if n < answer:
                            answer = n
                    if station_visited[l_list[s_list[i]][j]] == False: # 안 간 역
                        station_visited[l_list[s_list[i]][j]] = True
                        queue.append((n+1, l_list[s_list[i]][j]))
    if answer == 1000000:
        print(-1)
    else:
        print(answer)

if start == end:
    print(0)
else:
    bfs()

 

풀면서 느꼈지만 어떻게 데이터를(리스트를) 저장해주고 시작할지도 문제 푸는 방향에 큰 영향을 미치는 거 같습니다. 더 효율적이고 쉽게 풀고 싶다면 처음에 저장부터 신경써야할 필요성을 느꼈습니다.