최소 환승 경로

면접 대비

시간 제한1초메모리 제한256 MB

요약
여러 지하철 노선의 정차역 목록이 주어질 때, 출발역에서 목적역까지 가는 데 필요한 최소 환승 횟수를 BFS로 구합니다.
난이도

보통10점 중 5점

유형
BFS, 그래프, 구현
정답자
아직 제출이 없습니다

문제

어떤 도시의 지하철 노선 정보가 주어진다. 출발역에서 목적지역까지 이동할 때 필요한 최소 환승 횟수를 구하는 프로그램을 작성하시오. 실제 이동 경로를 출력할 필요는 없으며, 환승 횟수만 출력하면 된다.

입력

첫째 줄에 역의 개수 N (1 <= N <= 100,000)과 노선의 개수 L (1 <= L <= 100,000)이 주어진다.

다음 L개의 줄에는 각 노선이 지나는 역 번호가 순서대로 주어진다. 각 줄의 마지막에는 -1이 주어진다.

마지막 줄에는 출발역 번호와 목적지역 번호가 주어진다. 역 번호는 1부터 N까지의 정수이다. 모든 노선 길이의 합은 1,000,000을 넘지 않는다.

출력

첫째 줄에 최소 환승 횟수를 출력한다. 목적지역에 도달할 수 없으면 -1을 출력한다.

예제1

  1. 예제 1

    입력
    10 3
1 2 3 4 5 -1
9 7 10 -1
7 6 3 8 -1
1 10
    예상 출력
    2