문제
어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.
이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.
예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.
이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.
해설
1. BFS vs DFS ?
BFS를 사용해 시작점으로부터 각 노드까지의 최단 거리를 구할 수 있다.
BFS는 너비 우선 탐색 알고리즘으로, 가까운 노드가 있다면 그 노드들을 모두 방문한다.
반면, DFS는 깊이 우선 탐색 알고리즘으로, 가까운 노드 중 하나만 먼저 방문한 후, 해당 노드와 이어진 노드들을 계속 깊숙히 탐색해나간다.
따라서 해당 문제에서는 BFS가 적절하다.
2. 사용할 자료구조
큐를 사용하면 먼저 들어온 노드번호에 대해 먼저 탐색할 수 있다. (선입선출)
가장 가까운 노드들부터 방문하기로 했으므로
현재 방문 중인 노드를 큐에 저장해두고, 다음 탐색 시에 큐에 저장된 노드들 중 가장 앞에 있는 노드를 꺼내 방문하는 방식이 필요하다.
3. 거리 계산
거리 리스트를 따로 두어 거리를 구할 수 있다.
초기화 시 모든 거리 값을 -1로 두고, 시작점의 경우 0으로 둔다.
예를 들어, 노드 개수가 4개이고 시작 노드번호가 1이라면
[-1, 0, -1, -1, -1, -1]
곧 방문할 노드의 시작점으로부터 거리 = 현재 방문 중인 노드의 거리 + 1 이라는 공식을 사용해 탐색해나간다.
예를 들어,
시작점인 1번 노드를 거쳐 2번 노드를 방문하고,
2번 노드를 거쳐 3번 노드에 방문하는 경우,
dist[2] = dist[1] +1 = 0 + 1 = 1 이고,
dist[3] = dist[2] + 1 = 1 + 1 = 2이다.
from collections import deque
def find_cities_with_distance_k(n, m, k, x, roads):
# 각 도시로 가는 최단 거리를 저장할 리스트
distance = [-1] * (n + 1) #[-1,-1,-1,....]
distance[x] = 0 # 시작 도시의 거리는 0으로 설정 #1이 시작점이라면 [-1,0,-1,....]
# 그래프 정보 저장 (도로는 단방향)
graph = [[] for _ in range(n + 1)] # [ [],[],... ]
for road in roads:
a, b = road #a, b = (1, 2)
graph[a].append(b) #[ [2],[] ... ]
# BFS 수행
queue = deque([x]) # deque는 양쪽으로 입력,출력이 가능한 클래스임. x를 처음 넣어 초기화 시 deque([x]) 로 사용.
while queue:
current_city = queue.popleft() # [ x, ... ] -> [ ... ]
# 현재 도시에서 이동할 수 있는 모든 도시 확인
for i in graph[current_city]: #x에 연결된 노드들 i
# 아직 방문하지 않은 도시라면
if distance[i] == -1:
# 최단 거리 갱신
distance[i] = distance[current_city] + 1 #현재 노드까지의 거리 +1
queue.append(i) #
# 최단 거리가 K인 도시 출력
result = [i for i in range(1, n + 1) if distance[i] == k]
if result:
for city in result:
print(city)
else:
print(-1)
# 입력 처리
n, m, k, x = map(int, input().split()) # 첫 번째 줄 입력 받기
roads = [tuple(map(int, input().split())) for _ in range(m)] # 도로 정보 입력 받기
find_cities_with_distance_k(n, m, k, x, roads)