[BOJ] 18352번 특정 거리의 도시 찾기

문제 링크

---

문제 요약

BFS/DFS 문제 에 해당한다.
특정 도시 X에서 출발하여 도달할 수 있는 모든 도시 중에서 최단 거리가 정확히 K인 도시들의 번호를 출력하는 문제이다. 입력으로는 도시의 개수 N, 단방향 도로의 개수 M, 출발 도시 번호 X, 그리고 정확히 도달해야 하는 최단 거리 K가 주어진다. 모든 도로의 거리는 1로 가정되며, 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

---

문제 풀이

✅ 비교적 간단하게 BFS 알고리즘을 이용하여 풀이할 수 있다. 다만, 출발하는 도시와 다른 도시들과의 거리를 계산해야하기 때문에 BFS/DFS를 다루는 것이 아직 서툴다면 어떻게 해야할지 고민이 될 수 있다.
방문 리스트 대신 거리 리스트를 만든다고 생각하면 훨씬 쉽게 접근이 가능한 문제다.

from collections import deque
import sys

# N: 도시의 개수, M: 도로의 개수, K: 거리 정보, X: 출발 도시의 번호

input = sys.stdin.readline
N, M, K, X = map(int, input().split())

city_map = [[] for _ in range(N+1)]

distance = [-1] * (N+1) # 거리 계산
distance[X] = 0

for _ in range(M):
    a, b = map(int, input().split())
    city_map[a].append(b)

# BFS 시작
queue = deque([X]) # 시작 도시 
while queue:
    current_city = queue.popleft()
    for nxt_city in city_map[current_city]:
        if distance[nxt_city] == -1: # 방문한적 없는 연결 노드라면
            queue.append(nxt_city)
            distance[nxt_city] = distance[current_city] + 1

Flag = False

for i in range(N+1):
    if distance[i] == K:
        print(i)
        Flag = True

if Flag == False:
    print(-1)

📌 고려해야할 점

import sys

input = sys.stdin.readline

위의 코드를 통해서 시간초과를 해결할 수 있었다. 코딜리티처럼 시간/메모리가 중요하게 작용하는 코테에서 유용하게 쓰일 것 같다.
또한, 처음에는 습관적으로 방문 기록을 위한 리스트를 작성했다가 메모리초과가 발생했는데 이는 거리 계산에서 -1 이라면 처음 방문한 도시라고 가정하고 문제를 푸는 것으로 해결했다.

• 딕셔너리에 방향어와 인덱스를 저장하여 접근하기
• 딕셔너리에 x, y좌표와 더불어 next x, next y도 함께 visitied에 저장해 중복을 체크해주는 것