본문 바로가기
Algorithm

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

by Yonghip 2022. 6. 19.
 

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

첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개

www.acmicpc.net

BFS 개념을 활용하면 풀 수 있는 흔한 문제이다.

from collections import deque
import sys
n, m, k, x = map(int, input().split())

graph = [[] for _ in range(n+1)]
for _ in range(m):
    start, end = map(int, sys.stdin.readline().split())
    graph[start].append(end)




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

def bfs(start):
    queue=deque()
    queue.append(start)
    distance[start] = 0
    while queue:
        city = queue.popleft()
        if distance[city] > k:
            break
        for i in graph[city]:
            if distance[i]==-1:
                distance[i] = distance[city]+1
                queue.append(i)

bfs(x)
if k not in distance:
    print(-1)
    sys.exit()
for i in range(len(distance)):
    if k == distance[i]:
        print(i)

대중적인 문제임에도 시간 초과를 5번은 넘게 본 것 같은데 처음엔 알고리즘을 잘못 짠 줄 알았다.
이유는 정말 단순하였는데...
문제를 보면 M(경로의 수)를 최대 1,000,000개를 입력받을 수 있어야 하는데
시간제한이 2초이므로 input()을 사용하면 시간 초과로 인하여 통과하지 못한다.
이 문제를 풀기 전까지는 계속해서 input( )을 사용하여 풀었기 때문에 이 점을 너무 간과하였다.

일정량 이상의 입력은 sys.stdin.readline(). rstrip()을 이용하여 받는다.

이 점만 주의하면 BFS 알고리즘을 사용하여 간단히 풀 수 있다.

추가적으로 readline() 뒤에 rstrip()를 붙이는 이유는 readline()을 사용하는 경우
이후의 "\n"까지 입력받기 때문이다.

'Algorithm' 카테고리의 다른 글

백준 2981번 검문  (0) 2022.12.02
백준 1929번 소수 구하기  (1) 2022.11.27
백준 1920번 수 찾기  (0) 2022.06.19
백준 1463번 1로 만들기  (0) 2022.06.19
백준 2178번 미로 찾기  (0) 2022.06.19