DFS/BFS 기출 문제 15. 특정 거리의 도시 찾기
1~N번까지의 도시와 M개의 단방향 도로가 존재한다. 특정한 도시 x로부터 출발하여 도달할 수 있는 모든
도시 중에서, 최단 거리가 정확히 K인 모든 도시의 번호를 출력하는 프로그램을 작성하세요.
답안 참고하였음.
n = 도시의 수
m = 도로 개수
k = 최단 거리
x = 출발 도시
이 문제 같은 경우에는 처음에 DFS로 풀다가, 이동 거리를 어떻게 처리해줘야할지 잘모르겠어서, 풀다가 답안을 보았다.
답안에서는 BFS로 해결하였다.
백준에서 이 문제의 질문 사항들을 보니 DFS로 해결하려한 사람들이 있는 것 같긴하던데, 고수분들께서 BFS로 해결하는 것이 실행 시간에서도 빠르다고 하셨다.
(아마 재귀를 안해도 되기 때문에?)
이제 답안에서 코드를 왜 그렇게 작성했는지 살펴보자
import sys
from collections import deque
n, m, k, x = map(int, sys.stdin.readline().split())
graph = []
for _ in range(n+1):
graph.append([])
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b)DFS/BFS 문제를 이제 3개밖에 안풀기도 하였고, 그래서 그래프 간의 연결 관계를 어떻게 다뤄야할 지 항상 고민을 많이 하는데,
이 문제 같은 경우에는, 인덱스를 도시의 번호로 지정하고, 각 인덱스에 다른 도시 번호를 리스트로 갖음으로써 연결 관계를 표현하였다.
city = [[ ], [2, 3]]예를 들어, 1번 도시가 2,3번 도시와 연결되어있다면 1번 인덱스에 2, 3을 리스트로 저장하였다.
그리고 각 도시들의 방문여부를 표현할 리스트를 생성하였다.
DFS/BFS 문제들에서 특히 방문 여부를 확인하기 위한 리스트를 생성하는 경우가 많다. 유의해두자
-1은 도시의 미방문을 표시하고, 시작하는 도시는 0으로 두었다.
cities = [-1]*(n+1)
cities[x] = 0현재 시작하는 도시 x를 큐에 넣고, BFS를 이용하여 해결한다.
반복문을 돌면서 큐에서 꺼내는 값은 현재 방문하는 도시가 되고,
for 문에서 현재 도시와 연결된 도시들을 처리한다.
연결된 도시의 값이 -1 이라면 방문하지 않았기 때문에, 방문하면서 값을 변경해준다.
이때 변경해주는 값은 해당 도시를 방문하기 위해 거쳐온 거리가 된다.
이렇게 되면 cities에 저장되는 값은 해당 도시를 방문하기 위한 최단 거리가 된다.
이 조건문을 처리할 때, cities[next_city] == -1 이 아닌 값은 어떻게 처리해야하나 고민했었는데,
문제에서는 도시를 방문하기 위한 최단 거리만 구하면 되기 때문에, -1 이 아닌 값들은
방문한 도시들이기 때문에 굳이 고려할 필요가 없는 것이다.
queue = deque([x])
while queue:
start = queue.popleft()
for next_city in graph[start]:
if cities[next_city] == -1:
cities[next_city] = cities[start] + 1
queue.append(next_city)check = False
for i in range(1, n+1):
if cities[i] == k:
check = True
print(i)
if not check:
print("-1")
