[Baekjoon/🥈SilverⅡ] 1260: DFS와 BFS

📃문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

📃입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

📃출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

🙋‍♀️접근 방법

👩 우선 문제에서 요구하는 DFS와 BFS가 무엇인지를 알아야 한다. 해당 개념에 대해서는 이전 18352: 특정 거리의 도시 찾기 문제를 풀이하면서 정리해보았다!!

👩 해당 문제에서 간선들은 모두 양방향이다. 즉, [1, 2]가 주어졌을 때, 1에서 출발해 2로 갈 수도 있으며, 2에서 출발해 1로 갈 수도 있다.

• 따라서 N개의 정점이 존재할 때, 간선의 존재여부를 기록하기 위해 N*N 리스트를 생성해야 한다.
• 양방향이므로 [1,2]가 간선으로 주어졌을 때는 1행 2열뿐만 아니라 2행 1열에도 간선이 존재함을 표시해야 한다.

🙋‍♀️ BFS: 넓이 우선 탐색

• 시작점이 1일 경우, 1과 연결된 모든 정점을 작은 수부터 차례로 탐색한다.

• 더이상 1과 연결된 정점이 없을 경우, 1 다음으로 탐색이 진행된 정점과 연결된 모든 정점을 탐색한다.
  • 해당 순서에 맞는 정점을 알맞게 가져오기 위해서는 양방향 큐인 deque을 사용한다.
• 그래프에 존재하는 모든 정점이 탐색될 때까지 위 과정을 반복한다.

🙋‍♀️ DFS: 깊이 우선 탐색

• 시작점이 1일 경우, 1과 연결된 가장 작은 정점을 다음으로 탐색한다.
  • 즉 해당 정점을 파라미터로 깊이 우선 탐색을 다시 진행한다. (재귀)
• 그래프에 존재하는 모든 정점이 탐색될 때까지 위 과정을 반복한다.

👩‍💻 Algorithm

👩 그렇다면 위 내용을 기반으로 작성한 코드를 살펴보자.

#21.11.01
import sys
from collections import deque

def dfs(v):
  global visit_lst1
  print(v, end=" ")
  visit_lst1[v] = 1
  for i in range(1, N+1):
  # 1부터 N까지의 정점을 확인하면 v와 간선이 존재하며, 아직 탐색되지 않은 정점일 경우를 찾는다.
    if visit_lst1[i] == 0 and graph[v][i] == 1:
      # 해당 정점을 기준으로 깊이 우선 탐색을 진행한다.(재귀!)
      dfs(i)

def bfs(v):
  global visit_lst2
  que = deque()
  que.append(v)
  visit_lst2[v] = 1
  while que:
    #deque에서 다음 탐색할 정점을 앞부분에서 꺼내온다.
    temp = que.popleft()
    print(temp, end=" ")
    #탐색이 이루어지지 않은 정점을 찾아 deque에 넣는다.
    for i in range(1, N+1):
      if visit_lst2[i] == 0 and graph[temp][i] == 1:
        que.append(i)
        visit_lst2[i] = 1


N, M, V= map(int, sys.stdin.readline().split())
graph = [[0] * (N+1) for _ in range(N+1)]
visit_lst1 = [0 for i in range(N+1)]
visit_lst2 = [0 for i in range(N+1)]

for _ in range(M):
  a, b = map(int, sys.stdin.readline().rstrip().split())
  graph[a][b] = graph[b][a] = 1

dfs(V)
print()
bfs(V)

👩 해당 문제를 해결하는데 생각보다 정말 오랜시간이 걸렸다. 풀이 방식은 쉽게 알 수 있었으나 자꾸 시간초과가 발생했다.

해당 문제를 풀이하면서 깊이 우선 탐색 알고리즘의 경우, 재귀를 주로 사용한다는 점을 알게 되었다. 또한, 이러한 탐색 알고리즘에서는 자료구조 deque가 유용하게 사용된다는 점을 이번 문제를 통해서 다시 한 번 확인할 수 있었다.

푼 날짜는 오래됐지만 정리는 이제야 한다..😶 한동안 알고리즘 공부를 하지 못했다😥😥 이제 다시 정신차리고 하루하루 꾸준히 풀어나가야겠다!!!

이번 게시글도!!!

여기서

이만 ~~ ~(˘▾˘~)

📃참고

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