Q15. 백준 18352 특정 거리의 도시 찾기

18352번: 특정 거리의 도시 찾기 (acmicpc.net)

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

 

순환없는, 모든 간선의 가중치가 1인 단방향그래프에서 특정 가중치를 갖는 노드만 찾아내는 문제다

기본적으로 BFS를 사용해서 해결할 수 있다.

 

from collections import deque

N, M, K, X = map(int,input().split())
#도시의 개수 N
#도로의 개수 M
#거리 정보 K
#출발 도시의 번호 X


graph = [[] for _ in range(N+1)]
for i in range(M):
    A, B = map(int, input().split())
    graph[A].append(B)

 

여기까지는 입력을 받는 부분이다.

그래프는 2차원 리스트 형태로 표현했다.

graph[A] = B일때 A노드에서 B리스트의 노드들로 가는 간선이 있다는 뜻. 노드는 숫자로 표현.

 

 

 

 

q = deque()
answer = [-1 for _ in range(N+1)]

 

bfs를 하기 위해서 queue가 필요한데

덱(deque)을 이용하면 앞뒤로 삽입이 가능해 큐랑 스택을 모두 쓸 수 있다.

사용법은 기본 자료형 list랑 크게 다를거없다. appendleft와 popleft가 있다는 점만 기억하면 사용 가능

 

정답 리스트에는 최단거리가 들어간다.

answer[i] = n 이라면 i번째 노드로 가는 최단거리가 n이라는 뜻이다.

지금은 -1로 초기화했지만 이제 아래 코드에서 최단거리를 구해 집어넣을 것이다.

 

 

 

q.append(X) # 시작노드를 집어넣는다.

while q: #큐에 뭐가 있으면
    city = q.popleft() #하나 꺼낸다

    if answer[city] == K: #최적화용 코드. 없어도 된다. 최단거리 K인 노드부터는 탐색 안하기
        continue

    for next_city in graph[city]: #다음 노드들에 대하여 (다음노드라 함은 간선이 연결된 노드)
        if answer[next_city] == -1: #아직 탐색이 안된 곳이면
            answer[next_city] = answer[city] + 1 # 최단경로를 추가하고
            q.append(next_city) #큐에 집어넣는다.

answer_existence = False # 정답이 존재하는지 여부

for i in range(1,N+1):
    if answer[i] == K: #최단거리가 K인 노드를 발견하면
        print(i) #출력한다
        answer_existence = True #그리고 정답존재여부는 True가 된다

if check == False: #정답이 없으면
    print(-1) #-1을 출력한다

 

근데 통과가 되지 않고 계속 시간초과가 뜬다..

책에서도 그렇고 인터넷에 있는 다른 사람들 해법도 그렇고 나랑 같은 bfs 알고리즘으로 풀었는데 왜 시간초과가 뜨는지 잘 모르겠다. C++로는 같은 알고리즘으로 해도 통과된다(역시 파이썬은 불리한 것인가.. 크흡..) 다른 분께서 작성한 다익스트라 솔루션을 써봤더니 통과됐다. 왜 그런걸까 ㅠ,ㅠ bfs 공부하려고 푼 문제인데 bfs로 통과가 안되니 영 찝찝하다;;