[이코테 Ch17-40] 숨바꼭질

👩🏻‍💻문제설명

[이코테 Ch17-40] 숨바꼭질

✍️Idea Sketch

문제요약

최단경로 중 가장 큰 값을 찾는 문제이다.
문제에서 "여기서 거리라 함은 지나야 하는 길의 최소 개수이다. " 라고 명시했다. 따라서 최단경로를 구하면 된다.

출발 헛간은 1번이다.
1번 헛간에서 x번 헛간까지의 최단경로를 모두 구하고, 그 중 가장 큰 값을 찾아야 한다.
가중치가 없고 모든 헛간을 탐색해야 한다.

시간복잡도

O(V + E)
BFS의 그래프를 인접리스트로 구현하면 총 O(V + E)의 시간복잡도를 가진다.

BFS는 모든 정점을 방문하므로 O(V)의 시간복잡도를 가진다. 이 때 한 정점을 방문할 때마다 간선을 통해 인접한 정점을 방문한다. 모든 간선도 방문하므로 O(E)의 시간복잡도를 가진다. 따라서 BFS의 총 시간복잡도는 둘을 합한 O(V + E)이다.

알고리즘 : BFS

최단경로를 모두 구하고, 그 중 가장 큰 값을 찾는 문제이다. 모든 정점을 탐색해야 하고 가중치가 없다. 따라서 BFS 너비우선탐색 알고리즘으로 구현한다.

✍️내 소스코드

• graph을 인접리스트로 구현한다.
• visited에 1번 헛간에서의 거리를 저장한다. 초기값은 -1이고, 출발지 1번 헛간의 visited 초기값은 0이다. 인접 헛간 y를 방문할 때마다 이전 헛간 x의 visited 값에 1을 더한 값을 저장한다.
• 최종적으로 숨어야 하는 헛간 번호 num, 그 헛간까지의 거리 leng, 그 헛간과 같은 거리를 갖는 헛간의 개수 cnt를 출력한다. visited를 바탕으로 계산한다.

전체 코드

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

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

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

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

  bfs(1)

  leng = max(visited)
  num = visited.index(leng)
  cnt = visited.count(leng)

  print(num, leng, cnt)