[백준/18352/파이썬] 특정 거리의 도시 찾기 _ 풀이

https://www.acmicpc.net/problem/18352

18352번: 특정 거리의 도시 찾기

---

풀이

# 최단거리이므로 큐 자료구조 사용
from collections import deque

# 도시수, 도로수, 거리, 출발도시번호 입력
n,m,k,x = map(int, input().split())
# 각 도시가 어느 도시와 이어져있는지 표시를 위해 2차원 리스트
graph = [[] for _ in range(n+1)]
# a번 도시에서 b번 도시로 이어진다는 것을 입력받아 구현
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)

# x에서 각 도시의 거리 정보에 대한 리스트를 구현
distance = [-1]*(n+1)
# x도시는 자기자신으로 0
distance[x] = 0

# 큐 선언
q = deque([x])

# 큐가 빌때까지 반복
while q:
    # 삽입된 순서대로 큐를 제거
    now = q.popleft()
    # 각 도시가 연결되어있는 도시를 선택
    for next in graph[now]:
        # 해당 도시의 거리가 -1로 입력되지않았을 때
        if distance[next]==-1:
            # 해당 도시까지 거리를 현재 도시로부터 +1 더해서 저장
            distance[next] = distance[now] + 1
            # 해당 도시를 큐에 삽입
            q.append(next)
# 플래그 변수를 초기화
check = False
# 거리 정보 리스트를 탐색
for i in range(len(distance)):
    # k와 같은 거리정보가 있을 때
    if k == distance[i]:
        # 그에 대한 인덱스를 출력
        print(i)
        # 플래그를 True로 변경
        check = True
# 반약 같은 거리정보가 없을 때
if check == False:
    # -1 출력
    print(-1)