이코테 339p
백준18352번

문제

• 제한
  • 시간 2초 / 메모리 256MB
• 입력
  • 첫째줄 : 도시의 갯수 N, 도로의 갯수 M, 거리정보 K, 출발 도시의 번호 K
    (2<=N<=300,000 / 1<=M<=1,000,000/1<=K<=300,000/1<=X<=N)
  • 둘째줄부터 : 두개의 자연수 A,B.
    A번 도시에서 B번도시로 이동하는 단방향 도로 존재한다는 뜻
    (1<=A / B<=N)
• 출력
  • X로부터 출발하여 도달할 수 있는 도시 중에서,
    최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력
  • 하나도 존재하지 않으면 -1 출력

풀이

당위성??

• 모든 간선의 비용이 동일할때, 모든 도시까지의 최단 거리를 재는데 BFS가 왜 사용되는지 이해하기
• 1씩 증가시켜서, 가는데의 거리 기록하는 방법 익숙해지기

시간복잡도

BFS의 시간복잡도는 O(N+M) (N=노드갯수, M=간선갯수)

노드 갯수 N은 최대 300,000
간선 갯수 M은 최대 1,000,000
O(N+M) 은 시간 2초 제한 안에 풀 수 있다.

풀이방법

1. 특정 도시 X를 시작점으로 BFS 수행하여 모든 도시까지의 최단거리 계산
2. 각 최단거리를 하나씩 확인하며 그 값이 K인 경우 해당 도시의 번호 출력

코드

from collections import deque

# 도시의 갯수, 도로의 갯수, 거리 정보, 출발 도시 번호
n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n+1)]

# 모든 도로 정보 입력받기
for _ in range(m) :
	a, b = map(int, input().split())
	graph[a].append(b)

# 모든 도시에 대한 최단 거리 초기화
distance = [-1] * (n+1)
distance[x] = 0 #출발 도시까지의 거리는 0으로 설정

# 너비 우선탐색 BFS 수행
q = deque([x]) # queue 생성

while q :
	now = q.popleft()
	# 현재 도시에서 이동할 수 있는 모든 도시를 확인
	for next_node in graph[now] :
		if distance[next_node] == -1 : # 아직 방문하지 도시일때
			distance[next_node] = distance[now] + 1 # 최단 거리 갱신
			q.append(next_node) # queue에 집어넣기

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

# 하나도 없다면 -1 출력
if check == False :
	print(-1)