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를 돌린다는 점을 주의해주면 된다.