문제
n개의 도시, m개의 단방향 도로가 존재
모든 도로의 거리는 1이다. 이때, 특정한 도시 x에서 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 k인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 n, m, k, x가 주어짐
둘째 줄부터 m개의 줄에 걸쳐서 두 개의 자연수 a, b가 공백을 기준으로 주어짐 이는 a에서 b로 이동하는 단방향 도로가 존재한다는 의미
출력
x에서 출발하여 도달할 수 있는 도시 중에서 최단 거리가 k인 모든 도시의 번호를 오름차순으로 출력
하나도 존재하지 않다면 -1을 출력
다익스트라로 풀리는 문제는 bfs로, bfs로 풀리는 문제는 다익스트라로 풀리는 경우가 많다!
(1) 다익스트라 알고리즘을 이용한 풀이
# dijkstra 풀이
import sys, heapq
n,m,k,x = map(int,sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]; INF = int(1e9)
for _ in range(m):
a,b = map(int,sys.stdin.readline().split())
graph[a].append(b)
def dijkstra(graph, start, target):
distance = [INF for _ in range(n+1)]
distance[start] = 0; result = []
hp = []; heapq.heappush(hp, (0,start))
while hp:
dist, node = heapq.heappop(hp)
if dist > distance[node]: continue
for x in graph[node]:
cost = distance[node] + 1
if distance[x] > cost:
distance[x] = cost
heapq.heappush(hp, (cost, x))
for i in range(1,len(distance)):
if distance[i] == target: result.append(i)
return result if result else [-1]
for r in dijkstra(graph, x, k): print(r)
(2) bfs 알고리즘을 이용한 풀이
# bfs 풀이
import sys
from collections import deque
n,m,k,x = map(int,sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]; INF = int(1e9)
for _ in range(m):
a,b = map(int,sys.stdin.readline().split())
graph[a].append(b)
q = deque(); q.appendleft(x); result = []
visited = [0 for _ in range(n+1)]
dist = 1; visited[x] = dist
# dist 1 = 0을 의미, 재방문 하는 경우를 없애기 위함
while q:
x = q.pop(); dist = visited[x] + 1
for node in graph[x]:
if visited[node] != 0: continue
q.appendleft(node)
visited[node] = dist
for i in range(1,len(visited)):
if visited[i]-1 == k: result.append(i)
if not(result): print(-1)
else:
for x in result: print(x)
# 반례
# 2 2 2 1
# 1 2
# 2 1