[이코테 Ch13-15] 특정 거리의 도시 찾기 (BFS)

👩🏻‍💻문제설명

[이코테 Ch13-15] 특정 거리의 도시 찾기 (BFS)

✍️Idea Sketch

시간복잡도

그래프를 인접리스트로 구현한 경우 O(V + E)이다.

• BFS에서 모든 정점을 방문한다. 한 번 방문한 정점은 다시 방문하지 않는다. (V = vertex = 정점)

• BFS에서 한 정점을 방문할 때마다 간선으로 인접한 정점을 방문한다. 한 번 지나간 간선은 다시 지나가지 않는다. (E = edge = 간선)

• 따라서 그래프를 인접리스트로 구현한 경우, 시간복잡도는 O(V + E) 이다.

알고리즘 : BFS

도시의 최단 거리를 구해야 하는 문제이므로 BFS 알고리즘을 구현하면 된다.

✍️내 소스코드

• graph 인접리스트를 만들고 bfs 함수를 실행한다.
• 배열 visited는 도시의 최단 거리를 저장한다. 새롭게 방문한 도시 y의 visited 값은 이전에 방문한 도시 x의 visited 값 + 1이다.
• 배열 city는 최단 거리가 K인 도시의 번호를 저장한다. 최단 거리가 k인 경우 city 배열에 추가하고, 최단 거리가 k보다 클 경우에는 bfs 함수를 종료한다.

전체 코드

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

  n, m, k, x = map(int, si().split())
  graph = [[] for _ in range(n + 1)]

  for _ in range(m):
    a, b = map(int, si().split())
    graph[a].append(b)


  def bfs(k, x):
    queue = deque([x])
    visited[x] = 0
    city = []

    while queue:
      x = queue.popleft()
      for y in graph[x]:
        if visited[y] == -1:
          visited[y] = visited[x] + 1
          queue.append(y)

          if visited[y] == k:
            city.append(y)
          elif visited[y] > k:
              return city

    return city


  visited = [-1] * (n + 1)
  city = bfs(k, x)

  if city:
    for x in sorted(city):
      print(x)
  else:
    print(-1)