BFS와 DFS (백준 1260)

1. 그래프 언어 정리

 

2. BFS와 DFS

BFS와 DFS는 그래프 순회(traversal) 알고리즘 중 가장 기본적인 두 가지 방법입니다.

출처 https://namu.wiki/w/BFS

 

BFS(Breadth-First Search)

• 너비 우선 탐색
• 시작 노드로부터 시작하여 깊이(depth)가 낮은 노드부터 탐색을 진행하며, 같은 깊이의 노드들은 순서에 상관 없이 방문합니다.
• BFS는 큐(Queue) 자료구조를 이용하여 구현할 수 있습니다.
• BFS는 최단 경로를 찾을 때 사용하면 유용합니다.

DFS(Depth-First Search)

• 깊이 우선 탐색
• 시작 노드로부터 한 방향으로 탐색을 진행하다가 더 이상 탐색할 수 없는 경우, 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 탐색을 진행합니다.
• DFS는 스택(Stack) 자료구조 또는 재귀함수를 이용하여 구현할 수 있습니다.
• DFS는 그래프의 특정 부분을 탐색할 때 사용합니다.

 

3. 코드

예제는 백준 알고리즘 기본 문제입니다.

문제

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

입력

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

출력

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

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

1260번: DFS와 BFS

 

- 풀이

1. 정점수*정점수 그래프를 만들어 이어져 있는 칸을 1로 표시합니다.

아래 그래프에서 0은 코드에서 그래프를 표현하는 배열 인덱스와 실제 노드 번호를 일치시키기 위해서 입니다.

graph

2. (DFS, BFS 공통) 방문한 점을 표시하는 (visited)배열을 만듭니다.

 

- DFS

1. 노드를 방문하면서 visited 배열에 표시합니다.

2. 간선으로 이어진 노드 중 visited배열에 없는 것이 있다면 방문합니다.

-BFS

1. visited 배열과 함께 q를 생성하고 시작노드를 넣습니다.

    * q는 FIFO(Frist In Frist OUT)   선입선출 방법의 자료구조

2. q에서 노드를 pop합니다.

3. 꺼낸 노드에서 방문가능한 노드를 모두 visited배열에표시하고 q에도 넣습니다.

 

- 코드

위의 풀이를 실제로 구현한 코드입니다.

# N(node), M(edge), V(start)
N,M,V = map(int, input().split());

#초기 형태 set
graph = [[False] * (N + 1) for _ in range(N + 1)]

for i in range(M) :
  a, b = map(int, input().split());
  graph[a][b] = graph[b][a] = True

#DFS 재귀
def dfs(v):
  global visited
  visited[v] = True
  print(v, end = ' ')
  for i in range(1, N+1):
    if not visited[i] and graph[v][i]: dfs(i)

#BFS queue
def bfs(v):
  global q, visited
  q = [v]
  visited[v] = True
  while q:
    cur = q.pop(0)
    print(cur, end = ' ')

    for i in range(1, N+1):
      if not visited[i] and graph[cur][i]:
        visited[i] = True
        q.append(i)


visited = [False] * (N + 1)
dfs(V)
print() #줄 바꿈

visited = [False] * (N + 1)
bfs(V)

 

**자바스크립트추가** 

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let N, M, V;
let graph, visited, q;

rl.question('Enter N, M, V: ', (input) => {
  [N, M, V] = input.split(' ').map(Number);
  
  graph = Array.from({ length: N + 1 }, () => Array(N + 1).fill(false));
  visited = new Array(N + 1).fill(false);

  rl.on('line', (line) => {
    const [a, b] = line.split(' ').map(Number);
    graph[a][b] = graph[b][a] = true;
    M--;
    if (M === 0) {
      rl.close();
    }
  });
});

rl.on('close', () => {
  dfs(V);
  console.log();
  
  visited = new Array(N + 1).fill(false);
  bfs(V);
});

function dfs(v) {
  visited[v] = true;
  process.stdout.write(v + ' ');
  for (let i = 1; i <= N; i++) {
    if (!visited[i] && graph[v][i]) dfs(i);
  }
}

function bfs(v) {
  q = [v];
  visited[v] = true;
  while (q.length > 0) {
    const cur = q.shift();
    process.stdout.write(cur + ' ');

    for (let i = 1; i <= N; i++) {
      if (!visited[i] && graph[cur][i]) {
        visited[i] = true;
        q.push(i);
      }
    }
  }
}

4. 문제 유형

BFS: 그래프에서 최단 경로 문제,  최소 스패닝 트리, 웹 크롤러, 미로 찾기 문제 등에 사용됩니다. 

DFS: 그래프에서 사이클이 있는지 여부를 판별하는 문제, 경로의 특징을 저장해야 하는 문제, 그래프에서 모든 경로를 탐색하는 문제에 적합합니다(조합, 순열). 또한, 백트래킹과 조합 최적화 문제에도 사용됩니다.