DFS와 BFS

solved_ac[Class3][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부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 1

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1

1 2 4 3
1 2 3 4

예제 입력 2

5 5 3
5 4
5 2
1 2
3 4
3 1

예제 출력 2

3 1 2 5 4
3 1 4 2 5

예제 입력 3

1000 1 1000
999 1000

예제 출력 3

1000 999
1000 999

문제 해석

DFS와 BFS를 완벽하게 이해하고 있어야 한다. DFS와 BFS의 기초 문제이다.

DFS와 BFS 강의 영상

출처 [나동빈 님의 이코테 DFS,BFS]
{% include video id="7C9RgOcvkvo" provider="youtube" %}

DFS

• DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다.

• DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은 다음과 같습니다.

  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다.
  2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다.
  3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.

위 그림의 구현 코드

# 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)
# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

실행 결과

1 2 7 6 8 3 4 5
{: .notice--info}

BFS

• BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘입니다.
• BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같습니다.
  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다.
  2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리합니다.
  3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다.

위 그림의 구현 코드

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
  # 큐(Queue) 구현을 위해 deque 라이브러리 사용
  queue = deque([start])
  # 현재 노드를 방문 처리
  visited[start] = True
  # 큐가 빌 때까지 반복
  while queue:
    # 큐에서 하나의 원소를 뽑아 출력하기
    v = queue.popleft()
    print(v, end=' ')
    # 아직 방문하지 않은 인접한 원소들을 큐에 삽입
    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True

  # 각 노드가 연결된 정보를 표현 (2차원 리스트)
  graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
  ]
  
  # 각 노드가 방문된 정보를 표현 (1차원 리스트)
  visited = [False] * 9

  # 정의된 BFS 함수 호출
  bfs(graph, 1, visited)

실행 결과

1 2 3 8 7 4 5 6
{: .notice--info}

풀이

첫 번째 풀이

[틀린 풀이]

• graph 2차원 배열 초기화 graph = [[] for _ in range(N+1)]
• 각 정점들이 만나는 node를 graph[정점]에 넣어주기.

예제 1

ex) 1, 2 입력

=> graph[1].append(2)

=> graph[2].append(1)

**각 정점들이 연결되어 있으므로 교차로 집어 넣어야 함.**

결과

graph = [
  [],
  [2, 3, 4],
  [1, 4],
  [1, 4],
  [1, 2, 3]
]

위의 2차원 배열의 0번지를 비워놓은 이유는 입력 받은 번호에 0이 없기 때문에 코드의 가독성을 위해서 비워 놓았다.

graph[1]을 보면 2,3,4 가 있는데 1번 노드와 연결되어 있는 노드들이 2번 3번 4번이 있다는 얘기이다.

마찬가지로 graph[2]를 보면 1,4 가 있는데 2번 노드가 1번 노드와 4번 노드와 연결되어 있다는 뜻이다.

[예제 1. graph 도식화]

[예제 1. bfs와 dfs 동작 과정]

예제 2

[예제 2. graph 도식화와 bfs, dfs 동작 과정]

위의 예제 2번 그림에서 동작하는 것처럼 코드를 짜게 되면 답이 틀리게 된다.

그 이유는 작은 번호대로 방문을 해야 하는데, 입력 받은 걸 그대로 graph에 넣어주면 내림차순, 오름차순도 아니게 된다.

그래서 graph[i]마다 sort()를 해서 내림차순으로 만들어줘야 한다.

for j in range(1, N+1):
  graph[j].sort()

두 번째 풀이

[맞는 풀이]

BFS

• 첫 출발 노드 V를 queue에 넣어준다.
• 출발 노드를 방문 했으니 visit[V] = True로 바꾸어준다.
• queue가 빌 때 까지 while문을 돌리면서 큐에 먼저 들어간 숫자를 popleft()한다.
• popleft한 노드 주변 노드들을 for문으로 탐색한다.
• 그 중 방문하지 않은 노드에 먼저 가서 queue에 넣어준 후 그 노드는 방문 처리를 해준다.

DFS

• 첫 방문 노드는 방문 처리를 해준다.
• stack에 직접 넣어주는 대신 바로 print를 해준다. (print가 스택의 역할을 하는 것)
• 첫 방문 노드 인접 노드들을 탐색하면서 방문 하지 않은 노드를 먼저 찾아가 재귀 함수를 호출해준다.

import sys
from collections import deque

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

for i in range(M):
  a, b = map(int, sys.stdin.readline().split())
  graph[a].append(b)
  graph[b].append(a)
for j in range(1, N+1):
  graph[j].sort()

visit = [False] * (N + 1)
visited = [False] * (N + 1)

def bfs(graph, visit, start):
  queue = deque([start])
  visit[start] = True

  while queue:
    a = queue.popleft()
    print(a, end = ' ')
    for i in graph[a]:
      if not visit[i]:
        visit[i] = True
        queue.append(i)

def dfs(graph, visited, start):
  visited[start] = True
  print(start, end = ' ')

  for i in graph[start]:
    if not visited[i]:
      dfs(graph, visited, i)

dfs(graph, visited, V)
print()
bfs(graph, visit, V)

[주의 사항]

첫 번째 풀이부터 보셔야 두 번째 풀이가 이해가 갑니다.