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

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

어떤 나라에는 1~N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시의 번호를 출력하는 프로그램을 작성하여라. 또한 출발 도시 X에서 출발 도시 X로 가는 최단거리는 항상 0이라고 가정한다.

입력조건

• 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시 X가 주어진다.(2 <= N <= 300,000 , 1 <= M <= 1,000,000 , 1 <= K <= 300,000 , 1 <= X <= N)
• 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 주어지며, 각 자연수는 공백으로 구분한다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미이다.(1 <= A,B <= N) 단, A와 B는 서로 다른 자연수이다.

출력조건

• X로부터 출발하여 도달할 수 있는 도시 중에서 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다.
• 이 때 도달할 수 있는 도시 중에서 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.

사고과정

• BFS 문제인데 DFS 문제로 오판하여 매우 헤맸다. 주어진 그래프 데이터 정보를 인접 리스트 형태로 만든 것 까지는 잘했지만, 어떤 문제의 근거로 DFS인지 판단했는지는 아무생각없이 그랬던 것 같다. 그래서 제한 시간 내 풀이를 하지 못했다.
• 풀이를 보니 "모든 간선(문제에서는 도로)의 비용이 동일할 때는 BFS를 활용해서 최단 거리를 찾을 수 있다" 고 한다. 이게 문제에서 의미하는 "BFS를 이용해라~!" 라는 의미로 해석해야 한다. 따라서 해당 조건을 암기해놓고 해당 조건이 나오면 BFS를 활용할 것이라는 걸 조심스레 예상해보자.
• distance 로 최단 거리를 계산하는 빈 리스트는 정의를 잘했지만, 원소를 -1로 시작해서 방문 여부를 체크하고 동시에 최단 거리를 계산할 수 있도록 하지 못했다. 즉, 빈 리스트를 정의하되 초기 원소값을 무엇으로 정의하느냐가 또 하나의 관건인 듯 싶다.

풀이(스스로 풀지 못함)

import sys

from collections import deque
n, m, k, x = map(int, input().split())
graph = []
for _ in range(n+1):
    graph.append([])

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
# -1 -> 방문 여부도 계산하기 위함,  최단거리 계산할 리스트 정의(index 값이 도시번호를 의미)
distance = [-1] * (n+1)
distance[x] = 0  # 시작도시 -> 시작도시 가는 거리 = 0

queue = deque([x])
while queue:
    node = queue.popleft()
    # 인접 노드 탐색
    for next_node in graph[node]:
        # 인접 노드가 방문하지 않았다면 거리 계산(why? 한번이라도 방문했으면 거리 비용이 1로 더이상 업데이트 되면 안 됨)
        # 큐에 삽입
        if distance[next_node] == -1:
            distance[next_node] = distance[node] + 1 # 거리 계산법
            queue.append(next_node)

check = False
for city, dist in enumerate(distance):
    if dist == k:
        print(city, end=' ')
        check = True

if not check:
    print(-1)

 

추가적으로, 이후에 배운 최단 경로 알고리즘인 우선순위 큐(heapq)를 활용한 다익스트라 알고리즘을 활용한 소스코드도 첨부해 놓는다.

 

import heapq

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, 1))

INF = int(1e9)
distance = [INF] * (n+1)

def dijkstra(start):
    q = []
    distance[start] = 0
    heapq.heappush(q, (0, start))
    while q:
        dist, node = heapq.heappop(q)
        if dist > distance[node]:
            continue
        for next in graph[node]:
            cost = distance[node] + next[1]
            if cost < distance[next[0]]:
                distance[next[0]] = cost
                heapq.heappush(q, (cost, next[0]))


dijkstra(x)
flag = True
for i in range(1, n+1):
    if distance[i] == k:
        print(i)
        flag = False
if flag:
    print(-1)