문제

꽉꽉나라에 사는 주예와 방주는 점 S에서 만나 저녁을 먹기로 했다. 주예는 점 S에 도착했지만 길치인 방주가 약속시간이 30분이 지나도 나타나지 않자 방주에게 연락을 하여 방주가 점 E에 있다는 사실을 알아냈다. 주예는 방주에게 그 위치에 가만히 있으라고 했고, 직접 점 E로 가려고 한다.

꽉꽉나라에는 1부터 N까지의 각 점에 하나의 텔레포트 정거장이 위치해 있고 텔레포트를 통하여 연결되어 있는 다른 텔레포트의 정거장으로 이동할 수 있다. 주예는 현재 위치가 점 X라면 X+1이나 X-1로 이동하거나 X에 위치한 텔레포트와 연결된 지점으로 이동할 수 있으며 각 행동에는 1초가 소요된다. 배가 고픈 주예는 최대한 빨리 방주와 만나고 싶어 한다.

N과 텔레포트 연결 정보가 주어질 때 점 S에 있는 주예가 점 E까지 가는 최소 시간을 구해보자.

import sys

input = lambda: sys.stdin.readline().strip()

from collections import deque

n, m = map(int, input().split())
s, e = map(int, input().split())
graph = []
for _ in range(n + 1):
  graph.append([])
for _ in range(m):
  x, y = map(int, input().split())
  graph[x].append(y)
  graph[y].append(x)

visited = [False] * (n + 1)


def bfs(s, e, count=0):
  queue = deque()
  queue.append((s, e, count))
  while queue:
    s, e, count = queue.popleft()
    visited[s] = True
    if s == e:
      return count
    if 0 <= s + 1 <= n and visited[s + 1] == False:
      visited[s + 1] = True
      queue.append((s + 1, e, count + 1))
    if 0 <= s - 1 <= n and visited[s - 1] == False:
      visited[s - 1] = True
      queue.append((s - 1, e, count + 1))
    for g in graph[s]:
      if visited[g] == False:
        visited[g] = True
        queue.append((g, e, count + 1))


print(bfs(s, e))

백준 18232 텔레포트 정거장