[백준] 18352-특정 거리의 도시 찾기 BFS (Python3)

- 이것이 취업을 위한 코딩 테스트다 - 를 공부해보자 (ch.13)

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

1~N번까지 도시, M개의 단방향 도로

모든 도로의 거리는 1

 

특정한 도시 X로부터 출발해 도착할 수 있는 모든 도시 중

최단 거리가 정확히 K인 모든 도시의 번호를 출력

 

---

 

처음에 visited 배열을 사용하려고 했는데,

 

이 문제 입력 자체가 graph의 간선을 입력받는 형태인걸 간과했다

 

그래서 q.popleft()로 구한 현재 노드를 바탕으로 graph[노드]의 값을 탐색하며

not visited이면 True로 바꾸고 queue에 append하도록 했더니

1->2, 1->3인 경로를 모두 추가해서, 거리가 1만 증가해야 하는 상황에서도 2가 증가해버리는 상황이 나왔다

 

해답을 보니, 이건 visited boolean 배열이 아니라

distance 배열을 만들어서 -1값으로 초기화한 후,

해당 노드와 연결된 노드들에 지금 노드에서 가지고 있는 거리값을 누적해서 더해주는 형태로 풀어야 했다

 

그래서 1->2, 1->3 같은 경우에도 이 둘을 합쳐서 1을 더하는게 아니라

이 노드와 연결된 다음 노드들에 거리 1씩만 더하게 되기 때문이다

 

from collections import deque



n,m,k,x = map(int, input().split())

graph = [[] for _ in range(n+1)]

for i 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:
    cur = q.popleft()
    for next in graph[cur]:
        if distance[next]==-1:
            distance[next]=distance[cur]+1
            q.append(next)
check=False
for i in range(1,n+1):
    if distance[i]==k:
        print(i)
        check=True
if check==False:
    print(-1)

 

근데 그나저나 이거 python3으로 하면 시간초과 뜨고 pypy3으로 해야 통과하더라

더 최적화가 필요한 듯 싶다

 

풀이 시작: 11.08. 09:50

풀이 종료: 11.08. 10:40