백준 18352(특정 거리의 도시 찾기) - Python(파이썬) -BFS

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

풀이 방법 

모든 도로의 거리가 1이므로 -> bfs 가능하다. 

① graph(노드와 간선을 나타내는 그래프) (연결 여부 확인용)으로 사용한다

-> a와 b가 연결되었다고 가정하면 graph[a] = [b] 이렇게 있도록.

② 거리 테이블을 표현하는 테이블 하나 선언하기 (distance) , 이때, 초기값들은 모두 -1이도록 선언

③ 시작노드부터 시작하여서 연결된 노드들의 값이 -1인경우(처음 방문하였으므로) 현재 노드의 distance+1

④ 출력값이 K와 일치한 노드를 찾는 것이므로 거리 정보 K와 일치한 값일 경우 check =false에서 true가 되게 하고 그 때의 노드 값 출력, check=false인 경우에는 일치하는 노드가 없으므로 -1을 출력

 

파이썬으로 푼 경우 ) 

import sys
from collections import deque

#도시의 개수, 도로의 개수, 거리정, 출발 도시 번호
n,m,k,x = map(int,sys.stdin.readline().split())
#도시의 개수만큼 그래프에 [[] [] [] [] ]이런식으로 만듬
#graph : 노드와 간선을 나타내는 그래프( 연결 여부 확인용 )
#헷갈리지 않게 n+1개라고 가정해서 노드 0도 있게 하기
graph=[[] for _ in range(n+1)]
for i in range(m):
    a,b = map(int,sys.stdin.readline().split())
    graph[a].append(b)

#최단 거리 테이블
distance =[-1]*(n+1)

def bfs(start):
    q = deque([start])
    distance[start]=0
    while q:#큐가 빌때까지 반복하기
        #현재 있는 곳 q에서 뽑기
        now = q.popleft()
        for i in graph[now]:#현재 값과 연결된 노드
            if distance[i]==-1:
                distance[i] = distance[now]+1
                q.append(i)

bfs(x)

check=False
for i in range(len(distance)):
    if distance[i]==k:
        check=True
        print(i)

if check==False:
    print(-1)