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

1. 문제 출처

https://www.acmicpc.net/problem/18352

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

2. 풀이

bfs(너비 우선 탐색)를 이용하여 구하였다.

 

제일 어려웠던점은 아이러니하게 알고리즘 구현이 아닌 시간 초과 문제 였다.처음에는 deque 대신 리스트에 pop()을 하는 형식으로 구현 하였으나 시간 초과가 발생하였다. 이를 deque 자료형을 불러와 popleft 를 대신 사용 하였더니 해결되었다......다음 부터는 deque를 애용해야 겠다..

from collections import deque
#입력값 받기
N, M, K, X = map(int, input().split())
X = X-1
road_list = [[] for _ in range(N)]


# index = 시작 도시 # value = 시작 도시에서 갈수 있는 도시 리스트
for _ in range(M):
    start_city,end_city  = list(map(int, input().split()))
    road_list[start_city-1].append(end_city-1)

# bfs
def min_distance():
	# 방문 리스트 초기화 
    visted = [-1 for i in range(N)]
    # 시작 도시는 0으로
    visted[X] = 0
    # bfs를 위한 queue
    queue = deque([X])
    while queue:
    # queue 에서 값 꺼내기(FIFO)
        city  = queue.popleft()
        for next_city in road_list[city]:
        # 만약 방문 하지 않았다면
            if visted[next_city] == -1:
            # 전 도시 +1 값을 저장(시작 도시로 부터 최단 거리)
                visted[next_city] = visted[city]+1
                # queue에 추가
                queue.append(next_city)

    check =True
    # K인 도시 출력
    for idx in range(N):
        if visted[idx] == K:
            print(idx+1)
            check = False
    if check:
        print(-1)
        

min_distance()