[이코테] DFS/BFS - 특정 거리의 도시 찾기

❓문제

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

💭 아이디어

이 문제에서 모든 도로의 거리는 1이다. = 모든 간선의 비용이 1이다.

그래프에서 모든 간선의 비용이 동일할 때는 너비 우선 탐색을 이용하여 최단 거리를 찾을 수 있다.

-> 따라서 해당 문제는 BFS를 통해 풀이하면 된다.

distance 배열을 생성하여 방문여부를 기록함과 동시에 도시까지의 최단거리를 갱신해준다.

	> distance 배열 값이 -1은 방문하지 않았음을 뜻하고 -1이 아닌 경우 이미 방문했음, 즉 이미 최단 거리로 기록되었음을 뜻하므로 신경쓰지 않아도 된다.

[입출력 예시 그래프]

내가 헷갈렸던 부분은 입출력예시와 같이 1->3 (거리 1)과 1->2->3 (거리 2)를 어떻게 구분하고 구현할지였던 것 같다. "최단 거리"라는 단어 자체가 두번째 케이스는 신경쓰지 않아도 됨을 뜻한다.

❗ 풀이

from collections import deque

n, m, k, x = map(int, input().split())

country = [[] for _ in range(n+1)] # 인접리스트 방식, n+1개의 행 생성
# print(country)

for i in range(m): # 도로의 개수만큼 입력
    a, b = map(int, input().split())
    country[a].append(b)
    # input_data = input().split()
    # country[int(input_data[0])].append(int(input_data[1]))

distance = [-1] * (n+1) # 모든 도시에 대해 최단 거리 초기화 (방문여부가 아닌 최단 거리 기록)
distance[x] = 0 # 출발도시까지의 거리는 0

queue = deque([x])

while queue:
    now = queue.popleft()
    for next_node in country[now]:
        if distance[next_node] == -1: # 아직 방문하지 않은 도시라면
            distance[next_node] = distance[now] + 1 # 최단거리 갱신
            queue.append(next_node)

check = False
for i in range(1, n+1):
    if distance[i] == k:
        print(i) # 인덱스 순서로 돌기 때문에 정렬 필요 없음
        check = True # 만족하는 도시가 하나 이상

if check == False:
    print(-1)

✅ Comment

단순 방문 여부만을 기록하는 것이 아닌 최단 거리를 기록하자. 이때 초기화를 0이 아닌 -1로 하고 출발 도시까지의 거리도 0으로 명확히 기록한다.

그래프에서 모든 간선의 비용이 동일할 때 최단 거리를 찾아야 한다면 BFS를 이용하자.

헷갈렸던 부분에 대해 다시 체크하고, 추후 재풀이를 진행하자!