[BOJ/백준] 2021 최소 환승 경로

import sys
from collections import deque
def input():
    return sys.stdin.readline().rstrip()
 
 
N,M = map(int,input().split())
 
 
graph = [[] for _ in range(N+1)]
 
 
 
for ind in range(M):
    arr = list(map(int,input().split()))
    lens = len(arr)
 
    for arr_ind in range(lens-1):
        cur_node = arr[arr_ind]
        if arr_ind == 0:
            graph[cur_node].append([-1,arr[arr_ind+1],ind])
        else:
            graph[cur_node].append([arr[arr_ind-1],arr[arr_ind+1],ind])
 
start_node, end_node = map(int,input().split())
INF = float('inf')
distance_list = [INF for _ in range(N+1)]
visited_node = [True for _ in range(N+1)]
distance_list[start_node] = 0
queue = deque()
 
queue.append((start_node,0,-1))
 
while queue:
    node,cnt,prev_ind = queue.popleft()
    for left_node,right_node,position in graph[node]:
        if left_node != -1:
            if prev_ind == -1:
                distance_list[left_node] = cnt
                queue.append((left_node,cnt,position))
            else:
                temp = 1 if prev_ind != position else 0
                if distance_list[left_node] > cnt + temp:
                    distance_list[left_node] = cnt + temp
                    queue.append((left_node,cnt+temp,position))
        if right_node != -1:
            if prev_ind == -1:
                distance_list[right_node] = cnt
                queue.append((right_node,cnt,position))
            else:
                temp = 1 if prev_ind != position else 0
                if distance_list[right_node] > cnt + temp:
                    distance_list[right_node] = cnt + temp
                    queue.append((right_node,cnt+temp,position))
 
 
 
 
if distance_list[end_node] == INF:
    print(-1)
else:
    print(distance_list[end_node])

 

처음 풀었던 풀이는 좋은 풀이는 아닌것처럼 보인다.

 

처음 풀었던 방식은 다음과 같다. 현재 노드에 좌우 노드와 현재 노선을 집어넣어준다.

 

그리고 bfs를 하면서 노선이 바뀔때 그 값이 현재 있는 값보다 적으면 바꿔서 queue에 넣어주는 방식대로 했다.

 

이 방식의 문제점은 한 노선이 엄청 길면 모든 노선들을 전부 하나하나씩 다 탐색을 하는 것이다.

 

import sys
from collections import deque
def input():
    return sys.stdin.readline().rstrip()
 
N,M = map(int,input().split())
 
graph = []
 
subway_routelist = [[] for _ in range(N+1)]
 
 
for route_ind in range(M):
    arr = set(map(int,input().split()))
    arr.remove(-1)
    for subway_num in arr:
        subway_routelist[subway_num].append(route_ind)
 
    graph.append(list(arr))
 
start_node, end_node = map(int,input().split())
visited = [-1 for _ in range(N+1)]
visited_subway = [-1 for _ in range(M)]
end_subway = []
 
for route_ind in range(M):
    if end_node in graph[route_ind]:
        end_subway.append(route_ind)
 
 
queue = deque()
route_cnt = 0
visited[end_node] = 0
for end_route in end_subway:
    visited_subway[end_route] = route_cnt
    for subway_num in graph[end_route]:
        if visited[subway_num] == -1:
            visited[subway_num] = route_cnt
            queue.append(subway_num)
 
if visited[start_node] != -1:
    print(0)
else:
        
    while queue:
        N = len(queue)
        for _ in range(N):
            node = queue.popleft()
            for route in subway_routelist[node]:
                if visited_subway[route] == -1:
                    visited_subway[route] = route_cnt + 1
                    for subway_num in graph[route]:
                        if visited[subway_num] == -1:
                            visited[subway_num] = route_cnt + 1
                            queue.append(subway_num)
        route_cnt += 1
        if visited[start_node] != -1:
            break
 
 
    print(visited[start_node])

 

 

이 풀이는 노선을 기준으로 bfs를 하는 방식이다.

 

먼저 사전 작업으로, subway_route_list에 현재 노선번호를 넣어준다.

 

graph에는 각 노선의 역정보를 넣어준다.

 

 

먼저 우리는 도착지점이 있는 route(노선)들을 전부 구한다. 그 노선이 있는 목록을 end_subway라고 하겠다.

 

그러면 우리는 이 route들의 모든 노선들은 환승이 없이 도착지점에 도착하는 것을 알 수 있다.

 

그러므로 우리는 visited_subway라는 노선의 방문을 체크하는 곳에 방문의 여부를 체크를 해준다.

 

그리고 난뒤에 우리는 이 노선(route)에 있는 역들도 전부 환승없이 방문 할 수 있는 것을 알 수 있다.

 

그러므로 역의 방문을 나타내는 visited에 방문을 체크해주고, 그때의 역번호를 queue에 넣어준다.

 

위와 같은 일련의 작업을 한뒤에는 우리가 구할 수 있는 것은 도착지점에서 한번의 환승도 없이 다닐 수 있는

 

모든 역들을 체크해준것이다.

 

그러면 우리는 현재 상태에서 start_node가 방문이 표시되었다 하면, 환승없이 start_node에서 end_node까지 갈수 있음을 알 수 있고,

 

그때는 0을 출력해준다.

 

만약 그렇지 않을때에는 bfs를 해주면 된다.

 

이 bfs는 하나의 queue 단위로 bfs를 돌려주면 되므로,

 

최초의 queue의 크기인 N만큼 popleft를 해주면서, 해당 역에서 갈 수 있는 노선을 갱신해주고,

 

이 노선에서 갈 수 있는 역 중에 가보지 않은 역들을 queue에 추가해주면된다.

 

이러한 방식을 통해 최소 환승 횟수를 알 수 있게 된다.

 

 

이 문제에서 주요한 점은 역을 중점으로 bfs를 돌리는 것이 아닌 노선을 중심으로 해서 bfs를 돌린다는 점을 주의해주면 된다.