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

백준(BOJ) - 특정 거리의 도시 찾기

문제풀이: BFS, 파이썬

해결방법

문제에서 모든 도로의 길이가 1이다. 그래프에서 모든 간선의 비용이 동일할 때는 BFS 를 이용해서 최단 거리를 찾아야 한다.

문제의 조건이 노드의 최대는 300,000개이며 간선의 최대는 1,000,000 으로 BFS를 사용했을 때 O(N + M)의 시간 복잡도로 해결할 수 있다.

from collections import deque

n, m, k, x = map(int, input().split())
city = [[] for _ in range(n+1)]
city[0] = [0]
count = [-1] * (n+1)

for _ in range(m):
    a, b = map(int, input().split())
    city[a].append(b)

q = deque()
q.append(x)
count[x] = 0

while q:
    node = q.popleft()
    for c in city[node]:
        if count[c] == -1:
            count[c] = count[node] + 1
            q.append(c)

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

if result is not True:
    print(-1)