[DFS/BFS] 특정 거리의 도시 찾기

문제링크

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

 

해설

1. 최단거리니까 bfs로 풀자
2. 최단 거리가 정확히 K인걸 찾아야 하므로 최단거리가 K 미만인 도시는 지워줘야 함

from collections import deque

# N, M을 공백으로 구분하여 입력받기
n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n+1)]

for i in range(m):
    start, end = map(int, input().split())
    graph[start].append(end)

distance = [-1] * (n+1)
distance[x] = 0 # 출발 도시의 거리는 0으로 설정

q = deque([x])
cnt = 0
while q:
    v = q.popleft()

    for i in graph[v]:
        if distance[i] == -1:
            distance[i] = distance[v] + 1
            q.append(i)


# 최단 거리가 K인 모든 도시의 번호를 오름차순으로 출력
check = False
for i in range(1, n+1):
    if distance[i] == k:
        print(i)
        check = True

# 만약 최단 거리가 K인 도시가 없다면, -1 출력
if check == False:
    print(-1)

 

• 시간 초과 오류 극복 : input 대신에 sys.stdin.readline을 이용해보자

import sys
input = sys.stdin.readline

 

총평/느낀점

• 고민해본 코드들이 왜 안 되는지 잘 모르겠어서 많이 애먹은 것 같다
• 아직도 bfs가 조금 어렵게 느껴지는 건 어쩔 수 없는 것 같다.
• 최대한 기본 bfs 구조에서 생각하고 약간 변형한다는 컨셉으로 풀자

 

출처

• 이것이 코딩테스트다
• 시간 초과 오류나면 고려해봐야 하는 사항
• https://lifeofyoori.tistory.com/54