BOJ 18352 - 특정 거리의 도시 찾기 (BFS)

16 Feb 2021 in ALGORITHM

‘풀이시간 30분 , 시간제한 2초, 메모리제한 256MB, 백준 18352번 (취코테 339p)’

Baekjoon 18352: 특정 거리의 도시 찾기
우선 도로의 길이가 동일한 도시에서 최단거리를 찾는 문제이므로 BFS를 이용해야한다.

그래프를 만들어주고, 첫 출발 도시 x의 거리 정보인 distance[x]를 0으로 초기화 해준다.
BFS를 통해 큐에서 꺼낸 도시에서 연결되어 있는 도시 중 방문한적 없는 곳이라면 방문하지 않은 도시인 i의 거리정보인 distance[i]를 큐에서 꺼낸 데이터 v의 거리 정보 distance[v]에 1을 더하여 거리정보를 갱신해준다.
이런식으로 모두 탐색을 하면 모든 도시의 거리정보가 distance에 저장이 된다. 따라서 distance에서 찾고자하는 거리인 도시가 있는지 순차적으로 확인하고, 찾았다면 도시를 출력한다. 없다면 -1을 출력한다.

from sys import stdin
from collections import deque

def bfs(graph, start, visited, k, distance):
  queue = deque([start])
  visited[start] = True

  while queue:
    v = queue.popleft()
    for i in graph[v]:
      if not visited[i]:
        distance[i] = distance[v] + 1
        queue.append(i)
        visited[i] = True

n, m, k, x = map(int, input().split())
exist = False
visited = [False] * (n + 1)
graph = [[] for _ in range(n + 1)]
distance = [-1] * (n + 1)
distance[x] = 0

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

bfs(graph, x, visited, k, distance)

for i in range(1, n + 1):
  if distance[i] == k:
    print(i)
    exist = True

if exist == False:
  print(-1)