[백준 18352번] 특정 거리의 도시 찾기

🦥 특정 거리의 도시 찾기

문제

출처 : 문제 링크

입력/출력

입출력 예제

풀이

🔎 아이디어

• 모든 간선의 값이 동일 = BFS 이용 → ‘모든 도로의 거리는 1’
• 도시 X를 시작점으로 BFS 수행하여, 모든 도시까지의 최단 거리를 계산
• 최단 거리를 하나씩 확인, 값이 K인 경우 출력

🔎 코드

  # 특정 거리의 도시 찾기
  from collections import deque  # 큐(Queue) 사용 라이브러리

  # 도시 개수, 도로 개수, 거리 정보, 출발 도시 번호(노드)
  n, m, k, x = map(int, input().split())

  # 리스트 컴프리헨션
  graph = [[] for _ in range(n+1)] 

  # 모든 도로 정보 입력
  for _ in range(m):
      a, b = map(int, input().split())
      graph[a].append(b)

  # 모든 도시에 대한 최단 거리 초기화
  distance = [-1] * (n+1)
  distance[x] = 0 # 출발 도시까지의 거리는 0으로 설정

  # BFS 수행
  q = deque([x])
  while q:
      now = q.popleft()
      # 현재 도시에서 이동할 수 있는 모든 도시를 확인
      for next_node in graph[now]:
          # 아직 방문하지 않은 도시라면
          if distance[next_node] == -1:
              distance[next_node] = distance[now] + 1
              q.append(next_node)

  # 최단 거리 K인 모든 도시의 번호를 오름차순으로 출력
  check = False
  for i in range(1, n+1):
      if distance[i] == k:
          print(i)
          check = True

  # 만약 최단 거리가 K인 도시가 없다면, -1 출력
  if check == False:
      print(-1)