[Baekjoon/🥈SilverⅡ] 18352: 특정 거리의 도시 찾기

Intro

• 입력
  • N: 도시의 수 (1~N)
  • M: 단방향 도로의 수
  • X: 시작점 도시 (1<= X <= N)
  • K: 구하고자 하는 최단 거리
• 출력: 최단거리가 K인 도시들을 차례로 출력한다.

🙋‍♀️접근 방법

최단거리가 K인 도시들을 출력하는 문제이므로 도시 X에서부터 시작해 모든 도시들에 대한 최단거리를 알아야한다.

모든 도로의 거리가 1이라는 가정이 존재하므로 해당 문제는 가중치를 1로 한 다익스트라를 사용해 해결할 수 있다.

또한, 모두 가중치가 1로 동일하므로 단순히 BFS(너비 우선 탐색)을 통해서도 해결할 수 있다.

🙋BFS(너비 우선 탐색) VS DFS(깊이 우선 탐색)

그렇다면 우선 그래프를 탐색하는 두가지 방식에 대해서 살펴보자.

그래프를 탐색하는 방법에는 두가지 방식이 존재한다.

• BFS(너비 우선 탐색)
• DFS(깊이 우선 탐색)

위 그래프를 탐색하고자 할때 우선 너비 우선 탐색를 적용해보자!

---

🙌BFS(너비 우선 탐색)

해당 탐색 방법은 이름 그대로 너비를 중심으로 탐색을 진행한다.

다음과 같이 그래프의 깊이를 단계로 표시한다면 1단계 -> 2단계 -> 3단계 -> 4단계순으로 탐색을 진행한다.

• 여기서 너비를 중심으로 왼쪽에서 오른쪽으로 탐색하기 때문에 A를 탐색한 후에는 2단계의 B와 C, 3단계의 D, E, F, 4단계의 G, H순으로 탐색이 마무리된다.

---

🙌DFS(깊이 우선 탐색)

그렇다면 깊이 우선 탐색의 결과는 어떨까?

아마 BFS 방식을 살펴보면서 DFS의 방식 또한 예측할 수 있었을 것이다!! 깊이 우선 탐색 방법 또한 이름 그대로 깊이를 중심으로 탐색을 진행한다.

그래프의 깊이를 단계로 표시한다면 1단계 -> 2단계 -> 3단계 -> 4단계순으로 탐색을 진행하는 것은 BFS와 동일하다.

• 여기서 깊이를 중심으로 탐색하기 때문에 시작점인 A에서부터 갈 수 있는 가장 높은 단계까지 탐색을 먼저 진행한다. 즉, A -> B -> D -> G가 먼저 탐색이 진행된다.

• 이 방식 또한, 기본적으로 왼쪽에서 오른쪽으로 탐색이 진행되므로 다음 진행할 수 있는 깊이 탐색이 이어서 진행된다. 즉, E -> H가 탐색된다.

• 마지막으로 C -> F가 탐색되면서 탐색이 끝나게 된다.

👩 해당 문제에서는 시작점에서부터 최단거리가 K인 도시들을 모두 출력하는 문제이므로 DFS가 아닌 BFS를 사용해 특정 단계에 있는 모든 정점을 출력하면 된다!

👩‍💻Algoritm: BFS(너비 우선 탐색)

그렇다면 BFS 방식을 적용해 알고리즘을 작성해보자!

#21.11.03
#BFS 사용
import sys
from collections import deque
# X로 시작해서 각 지점까지 갈 수 있는 최단 거리

N, M, K, X = map(int, sys.stdin.readline().split())
lst = [M+1 for _ in range(N+1)]
lst[X] = 0

#단방향 도로 저장
road = [[] for _ in range(N+1)]
for j in range(M):
  temp1, temp2 = map(int, sys.stdin.readline().split())
  road[temp1].append(temp2)

que = deque([X])
while que:
  // 덱에서 다음 탐색해야 할 대상을 꺼냄
  check = que.popleft()
  // 해당 정점에서 갈 수 있는 정점을 차례대로 탐색함
  for j in road[check]:
    // 이미 탐색이 이루어진 정점이 아닌 경우
    if lst[j] == M+1:
      que.append(j)
      lst[j] = lst[check] + 1

if K in lst:
  for i in range(1, N+1):
    if lst[i] == K:
      print(i)
else:
  print(-1)

---

👩‍💻code 분석

다음과 같은 그래프에 대한 입력에서 이중 리스트 road에 저장되는 값은 다음과 같다.

[[], [2, 3], [3, 4], [], []]

• 즉, 시작점의 index 값에 시작점으로 부터 갈 수 있는 정점들이 저장된다.

• deque를 사용해서 너비 우선 탐색을 진행한다. 그 과정을 살짝 살펴보자!

  • 시작점 1이 탐색의 대상일 경우

    

  • leftpop()으로 인해 2가 탐색의 대상일 경우

    

    • 3은 이미 존재하므로 4만 deque에 넣는다.

---

👩 이번 알고리즘은 풀이는 비교적 간단하지만 필자는 해당 문제를 해결하는데 많은 시간이 걸렸다.

처음 알고리즘을 작성할 때, deque를 사용하지 않고 별도의 lst와 index를 가리키는 변수를 따로 둠으로써 탐색의 대상을 선정하였다. 그 결과 여려 번의 시간초과 결과를 얻었다..ㅎㅎ

사용할 수 있는 라이브러리들을 더 익히고 필요할 때 적극적으로 사용할 수 있도록 더 공부해야겠다!!

이번 포스트는 여기서

이만!

끝! ~(˘▾˘~)

📃참고

• https://steadily-worked.tistory.com/646
• https://devuna.tistory.com/32