[백준 1260번] DFS와 BFS

문제 링크 >> https://www.acmicpc.net/problem/1260

 

 

📋 문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오.

단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다.

정점 번호는 1번부터 N번까지이다.

 

 

👉 입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다.

다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다.

어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다.

입력으로 주어지는 간선은 양방향이다.

 

 

👈출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다.

V부터 방문된 점을 순서대로 출력하면 된다.

 

 

💡 사용된 개념

✔️ DFS

깊이 우선 탐색(DFS, Depth-First Search)은 그래프에서 깊은 노드를 우선적으로 탐색하는 알고리즘이다.

 

출처 : https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

 

DFS는 특정 경로를 탐색하다 특정한 상황에서 최대한 깊숙이 들어가 노드를 방문한 후 더이상 방문할 노드가 없으면 다시 돌아가 다른 경로를 탐색한다.

 

DFS는 stack을 사용하며 구체적인 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리 한다.
2. 스택의 top에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리 한다. 방문하지 않은 인접 노드가 없으면 스택에서 해당 노드를 꺼낸다.
3. 2의 과정을 수행할 수 없을 때까지 반복한다.

 

✔️ BFS

너비 우선 탐색(BFS, Breadth-First Search)은 가까운 노드부터 탐색한다.

 

https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

 

BFS는 queue를 사용하며 구체적인 동작 과정은 다음과 같다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입한다.
3. 2의 과정을 수행할 수 없을 때까지 반복한다.

 

 

📝 풀이

import sys
from collections import deque

n, m, v = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]

for _ in range(m):
  v1, v2 = map(int, sys.stdin.readline().split())
  graph[v1].append(v2)
  graph[v2].append(v1)
  
for i in range(len(graph)):
  graph[i].sort()
  
visited_dfs = [False]*(n+1)
visited_bfs = [False]*(n+1)

def dfs(graph, v, visited):
  visited[v] = True
  print(v,end=' ')
  
  for i in graph[v]:
    if not visited[i]:
      dfs(graph, i, visited)
      
def bfs(graph, start, visited):
  q = deque([start])
  visited[start] = True
  
  while q:
    v = q.popleft()
    print(v, end=' ')
    
    for i in graph[v]:
      if not visited[i]:
        q.append(i)
        visited[i] = True
    
dfs(graph, v, visited_dfs)
print()
bfs(graph, v, visited_bfs)

 

DFS, BFS를 파이썬으로 풀어본 적이 없어서 개념을 잡을 겸 풀었다.

DFS, BFS 개념 잡으려 한 건데 의외로 제일 어려웠던 건 입력 데이터 처리였다.

 

정점 v에 대해 v와 연결된 다른 정점들의 정보를 저장하는 작업이 필요했다.

입력으로 들어오는 것이 정점 2개의 정보였고 이는 이 둘이 연결되어있다는 뜻이었다.

따라서 간선의 개수만큼 for문을 돌리며 입력을 받아 각 정점을 v1, v2라고 이름을 붙이고 graph[v1]에 v2의 정보를, graph[v2]에 v1의 정보를 삽입했다.

 

정점을 방문하는 경우 인접한 정점 중 번호가 작은 것부터 방문해야 한다.

따라서 이에 대한 처리도 따로 필요한데 2차원 배열을 어떻게 정렬해야 하는지 감이 잡히지 않았다.

lambda식을 이용하고 싶었는데 잘 모르겠어서 graph를 순회하며 그냥 요소를 하나씩 정렬해 주었다.

더 나은 방법이 있는지 계속 찾아봐야겠다.

 

✔️ DFS

def dfs(graph, v, visited):
  visited[v] = True
  print(v,end=' ')
  
  for i in graph[v]:
    if not visited[i]:
      dfs(graph, i, visited)

 

DFS는 연결 정보가 담긴 graph, 시작 정점인 v, 방문 정보를 담을 visited를 인자로 받는다.

우선 v를 방문했다는 의미로 visited[v]를 True로 바꿔준다.

방문 노드를 출력해야 하기 때문에 이곳에서 바로 방문한 정점 v를 출력해준다.

 

이후 v의 연결 정보를 확인하며 v의 인접 노드를 방문하지 않았다면 재귀함수로 dfs를 호출한다.

이때 시작 노드는 v의 인접 노드가 된다.

재귀함수의 호출을 통해 v의 인접 노드 -> v의 인접 노드의 인접 노드 -> v의 인접 노드의 인접 노드의 인접 노드 -> ... 로 깊이 파고든다.

 

✔️ BFS

def bfs(graph, start, visited):
  q = deque([start])
  visited[start] = True
  
  while q:
    v = q.popleft()
    print(v, end=' ')
    
    for i in graph[v]:
      if not visited[i]:
        q.append(i)
        visited[i] = True

 

BFS도 연결 정보가 담긴 graph, 시작 정점인 start, 방문 정보를 담을 visited를 인자로 받는다.

먼저 시작 정점인 start를 큐에 넣고 start를 방문했다는 의미로 visited[start]를 True로 바꿔준다.

 

while문을 돌면서 q에서 요소 하나를 빼 출력하고 v의 인접 노드 정보를 확인하며 방문하지 않은 인접 노드가 있다면 큐에 넣는다.

이때 큐에 넣는 과정이 해당 정점을 방문했다는 뜻이 된다.

더이상 방문할 v의 인접 노드가 없다면 큐에서 다시 요소 하나를 빼 v의 값을 갱신하고 이 v의 인접 노드 정보를 확인하며 방문한다.

 

 

 

 

🔍 참조

이것이 취업을 위한 코딩테스트다 with 파이썬(한빛미디어, 나동빈)