[python] 백준18352_특정 거리의 도시 찾기 (DFS&BFS)

문제

풀이

'모든 도로의 거리는 1'이라는 조건 덕분에 BFS를 이용하여 해결할 수 있다.

 

 

 

코드

from collections import deque

n,m,k,x = map(int,input().split())  # 도시 개수, 도로 개수, 거리 정보, 출발 도시 번호
graph = [[] for _ in range(n+1)]    # 도시 개수 만큼 graph 리스트 생성

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

distance = [-1]*(n+1)   # 모든 거리는 -1 로 초기화
distance[x] = 0         # 출발 도시 거리는 0

q = deque([x])          # 출발 도시를 큐에 넣고

while q:
    now = q.popleft()   # 현재 도시 pop 해서

    for next_node in graph[now]:                    # 현재 도시에서 연결된 도시(노드) 탐색
        if distance[next_node] == -1 :              # next_node를 방문하지 않았으면
            distance[next_node] = distance[now] + 1 # next_node의 최단거리 갱신
            q.append(next_node)                     # 큐에 next_node append해서 반복

check = False
for i in range(1, n+1):     # distance가 k인 도시 있으면 출력
    if distance[i] == k:
        print(i)
        check = True

if check == False:          # distance가 k인 도시가 하나도 없으면 -1 출력
    print(-1)