코딩테스트 특정 거리의 도시 찾기 문제풀이

이코테 특정 거리의 도시 찾기(level 1.5) 문제풀이

처음에 BFS로 못풀겠어서 그냥 플로이드 워셜 알고리즘으로 풀려는데 메로리 초과로 못풀고 , 곰곰이 생각보다가 BFS알고리즘에서 visited를 더해가는 걸로 풀었다

import sys
from collections import deque
input = sys.stdin.readline


INF = 1e9
N, M, K, X = map(int, input().split())
graph = [[] for _ in range(N+1)]
visited = [-1]*(N+1)
for i in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
queue = deque([X])
visited[X] = 0
while queue:
    v = queue.popleft() 
    print(v)
    for i in graph[v]:
        if visited[i] == -1:
            queue.append(i)
            visited[i] = visited[v] + 1 #여기가 핵심

cnt = 0
for i in range(1, N+1):
    if visited[i] == K:
        print(i)
        cnt += 1
if cnt == 0:
    print(-1)