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

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

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

 

그래프에서 모든 간선의 비용이 동일할 때는 bfs(너비우선 탐색)을 이용하여 최단거리를 찾을 수 있다. 

문제에서 '모든 도로의 거리는 1'이 모든 간선의 비용이 동일하다는 말.

처음에 깊이 우선 탐색으로 코드를 작성했다가 시간초과가 떠서 너비우선탐색으로 바꾸었다. pypy3으로 실행해야 시간초과가 안뜬다 

그리고 n,m의 수가 매우 커서 dfs로는 무리였다 

거리에 대한 정보를 담을 distance 리스트를 만든다 

 

-정답 풀이 

from collections import deque

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

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

q=deque([x])
while q:
    now=q.popleft()
    for next_node in graph[now]:
        if distance[next_node]==-1:
            distance[next_node]=distance[now]+1
            q.append(next_node)
            
check=False
for i in range(1,n+1):
    if distance[i]==k:
        print(i)
        check=True
        
if not check:
    print(-1)

-내가 푼 풀이(시간초과 발생)

n,m,k,x= map(int,input().split())
graph= [[] for _ in range(n+1)]
graph[0].append(0)
for _ in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
visit=[[0]*(n+1)]
answer=[]
def dfs(v,cnt):
    visit[v]=1
    if cnt==k:
        answer.append(v)
    for i in graph[v]:
        if not visit[i]:
            dfs(i,cnt+1)
    return answer
dfs(x,0)
answer.sort()
for i in range(len(answer)):
    print(answer[i])