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

*이것이 취업을 위한 코딩테스트다 with 파이썬 교재를 공부한 내용을 바탕으로 작성했습니다.

 

 

 

DFS (Depth-First Search)

: 깊이 우선 탐색, 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작하며 스택 자료 구조 이용,

재귀호출 알고리즘도 같이 많이 사용한다!

모든 노드를 방문하고자 할 때 

 

 

 

BFS (Breadth-First Search)

: 너비 우선 탐색, 가까운 노드부터 탐색하는 알고리즘이며 큐(선입선출)를 이용한다.

두 노드 사이의 최단 경로

ex) 최단거리 문제 

 

 

 

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

2606번: 바이러스

 

 

특정 거리의 도시 찾기

 

 

1. 문제

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다.  2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

---

 

2. 입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

---

 

 

3. 출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

---

 

 

 

- 우선 각 문제를 DFS와 BFS로 풀지 정하는 것부터 어려움이 느껴진다. 이거는 문제를 많이 풀어봐야 감이 잡힐 것 같다..!

이 문제는 출발 도시의 번호가 주어지고 그 거리로부터 최단 거리가 정확히 k인 모든 도시의 번호를 출력하는 문제이다.

생각을 해보면, 한 노드에서 계속 쭉 뻗어가면서 깊게 탐색하는 것이 아니라,

해당 노드에서 가까운 노드부터 탐색하면서 거리를 계산하는 것이 좋으므로 BFS를 이용해서 푸는 문제이다.

(모든 노드의 길이가 1이기 때문에 BFS로 풀 수 있다고 한다!)

 

 

 

 

- 1번 노드를 우선 큐에 넣고, 꺼낸다. -> 2번, 3번 노드 방문하고 거리계산(1), 큐에 집어 넣는다 -> 2번 노드 큐에서 꺼낸다 -> 3번, 4번 노드 방문하고 거리계산(4번: 거리 2), 큐에 4번을 집어 넣는다. -> .... 반복

 

 

 

 

코드)

 

import sysfrom collections import deque
 
f = sys.stdin.readline
 
n, m, k, x = map(int, f().split())
 
graph = [[] for _ in range(n + 1)]
# 모든 도로 정보 입력 받기
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
 
#BFS
distance = [-1] * (n + 1)
distance[x] = 0 # 출발 도시까지의 거리는 0으로 설정
 
q = deque([x])
while q:
  out = q.popleft()
  for next in graph[out]:
    if distance[next] == -1:
      distance[next] = distance[out] + 1
      q.append(next)
 
flag = 0
for i in range(1, n + 1):
  if distance[i] == k:
    print(i)
    flag = 1
 
if flag == 0:
  print(-1)
 

 

🥕  sys.stdin.readline 사용해야지 시간초과 안 난다!!