[bfs/백준] 18352번 : 특정 거리의 도시 찾기

- 문제 : https://www.acmicpc.net/problem/18352

 

스스로 푼 문제이고, Silver Level 2 문제이다

dfs로 풀려다가 시간초과, 메모리 초과가 나서 bfs로 풀었다 

 

data[b].append(a) 때문에 계속 출력 초과가 나다가 없애니까 바로 정답으로 떴다 

문제에서 단방향 도로라는 것에서 힌트를 얻을 수 있다 

 

- 정답 풀이 : 

 

from collections import deque

n,m,k,x = map(int,input().split())
data = [[] for _ in range(n+1)]

for _ in range(m):
    a,b = map(int,input().split())
    data[a].append(b)
    
visit = [0]*(n+1)
distance = [0]*(n+1)

def bfs(v):    
    queue = deque()
    queue.append(v)
    result = []
    while queue:
        x = queue.popleft()
        if distance[x] == k :
            result.append(x)
        elif distance[x] < k:
            for i in data[x]:
                if not visit[i]:
                    visit[i] = 1
                    distance[i] = distance[x] + 1
                    queue.append(i)
    return result               
                
visit[x] = 1
result = bfs(x)
if len(result) == 0 :
    print(-1)
else:
    result.sort()
    for i in range(len(result)):
        print(result[i])