특정 거리의 도시 찾기

다시 한번 기본적인 BFS 문제를 가져왔다. BFS 기본 그 자체여서 이 문제는 쉽게 풀 수 있을 줄 알았는데, 안일하게 생각한 탓에 1시간 정도 고민을 더 해야했다.

문제 분석

도시 간에 단방향 도로들이 M개 주어졌을 때, 특정 도시에서 최단거리가 K인 도시들을 모두 오름차순으로 출력하는 문제다. 간단한 BFS 문제로, deque를 활용해 선입 선출의 구조로 도시들을 탐색해 나가면 된다. 추가로, 도시 개수만큼의 길이를 가지는 check 리스트를 만들어 해당 도시까지의 최단거리들을 저장한다.

시간초과

처음에 구현을 할 때, 도시 간의 도로 정보를 그대로 리스트에 저장하고, 매번 이 리스트를 탐색하며 가능한 도로를 탐색했다.

    for c in city:
        ~~

이렇게 매번 deque에서 점을 뽑을 때 마다 city전체를 탐색해야 해서 시간복잡도가 증가했던 것이었다.

이를 해결하기 위해 dictionary를 사용했다.

city=dict()
for _ in range(m):
    a,b=map(int,read().split())
    if a in city: city[a].append(b)
    else: city[a]=[b]

이렇게 city라는 dictionary를 만들어 해당 점에서 갈 수 있는 도시들의 정보를 저장했다. 그러면 한 점에서 갈 수 있는 다른 점을 탐색할 때, 해당 점이 dict안에 있는지 없는지만 확인하면 되기 때문에 시간복잡도를 낮출 수 있다.


CODE

import sys
sys.stdin = open("input.txt","rt")
read=sys.stdin.readline

n,m,k,x=map(int,read().split())
city=dict()
for _ in range(m):
    a,b=map(int,read().split())
    if a in city: city[a].append(b)
    else: city[a]=[b]
#print(city)
# n - #city
# m - #road
# k - how far
# x - start from

from collections import deque
save=deque([x])

check=list(-1 for _ in range(n))
check[x-1]=0
answer=[]

while save:
    a=save.popleft()
    if a in city:
        for c in city[a]:
            if check[c-1]==-1:
                save.append(c)
                check[c-1]=check[a-1]+1
                if check[c-1]==k: answer.append(c)

if answer:
    answer.sort()
    for a in answer: print(a)

else: print(-1)



CODE - 시행착오(시간초과)

import sys
read=sys.stdin.readline

n,m,k,x=map(int,read().split())
city= list(list(map(int,read().split())) for _ in range(m))
# n - #city
# m - #road
# k - how far
# x - start from
flag=2
from collections import deque
save=deque([x])
check=list(-1 for _ in range(n))
check[x-1]=0
while save:
    a=save.popleft()
    for c in city:
        if c[0]==a and check[c[1]-1]==-1:
            save.append(c[1])
            check[c[1]-1]=check[c[0]-1]+1
            if check[c[1]-1]==k:
                print(c[1])
                flag=1

if flag==2: print(-1)


[다시 풀어보기]