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

문제

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

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

이 문제의 알고리즘 분류는 다익스트라이기 때문에 다익스트라 알고리즘을 이용하여 풀려다가 모든 도로의 거리는 1이기 때문에 bfs 알고리즘을 사용해 문제를 풀었다.

 

내 코드

import sys
from collections import deque

n, m, k, x = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(n+1)]
distance = [0] * (n+1)
visited = [False] * (n+1)
q = deque()

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)

def bfs(start):
    city = []
    q.append(start)
    visited[start] = True
    while q:
        node = q.popleft()
        for i in graph[node]:
            if not visited[i]:
                q.append(i)
                visited[i] = True
                distance[i] = distance[node] +1
                if distance[i] == k:
                    city.append(i)

    if not city:
        print(-1)
    else: 
        city.sort()
        for i in city:
            print(i)

bfs(x)

이 문제를 푸는데 분명 테스트 케이스는 맞지만 계속하여 시간초과가 떴다..

코드에 오류는 없다고 생각하여 다른 사람의 코드를 보니 코드의 알고리즘이 똑같은데 왜 내 코드는 시간초과가 뜨는지 의문이 들었다.

 

내 코드가 시간초과였던 이유는 2가지였다.

 

1. input()

2. append()

 

다른 사람 코드를 보며 알게된 사실은 input()보다 sys.stdin.readline()이 더 빠르고 특히 한줄에 여러 입력을 받을 경우엔 더욱더 빠르다는 것이다.

또한 나는 visited리스트를 visited = [] 빈 리스트로 선언해주고 visited.append(i)를 하여 방문한 노드를 추가해주었다.

그런데 append()를 사용하는것 보다 visited = [0] * (n+1)로 선언하고 리스트의 인덱스를 이용해 접근하고 리스트를 수정하는것이 속도가 더욱 빠르다.

 

결국 이 두 문제 때문에 계속하여 시간초과로 틀렸던 것이다.

다른 문제를 풀때도 이 두가지로 유의하여 풀어야겠다.

https://breakcoding.tistory.com/109

[Python] 백준 시간초과 해결, 입출력 속도 개선