그래프(Graph) : 너비우선탐색(BFS) & 깊이우선탐색(DFS)

그래프

- 그래프란 노드(Node)와 간선(Edge)로 이루어진 연결 구조입니다.

- 노드는 점을 의미하고, 간선은 노드간 연결되어 있는 선을 의미합니다. 

 

가중 그래프

- 가중 그래프는 간선에 숫자를 부여해서 무게나 비용을 의미하게 만든 그래프입니다.

 

방향 그래프

- 방향 그래프는 간선에 방향을 부여해서 특정 방향으로만 이동할 수 있는 그래프입니다.

- 방향 그래프가 아닌 그래프는 양방향그래프라고 생각하면 됩니다.

- 가중 그래프처럼 비용, 무게를 부여할 수 있습니다.

 

 

너비 우선 탐색 (Breadth First Search)

- 시작점에서부터 목표점까지 갈 수 있는지 탐색하는 알고리즘입니다.

- 시작점에서 가까운 곳 부터 방문하는 알고리즘입니다.

- 선입선출 구조로 Queue(큐)를 주로 이용합니다.

 

ex) A에서 출발하여 E를 찾으시오.

1) 우선 가장 가까운 B와 C에 접근할 수 있습니다.

 

2) B에 접근한 상황이고, D, E에 접근할 수 있습니다.

3) C에 접근한 상황이고, F에 접근할 수 있습니다.

4) D에 접근한 상황이고, 추가로 접근 가능한 노드가 없습니다.

5) E에 접근한 상황이고, 원하는 도착지를 찾아서 탐색을 종료합니다.

 

 

깊이 우선 탐색 (Depth First Search)

- 시작점에서부터 목표점까지 갈 수 있는지 탐색하는 알고리즘입니다.

- 자식 노드가 존재한다면 자식노드를 먼저 탐색하는 알고리즘입니다.

- 후입선출 방식이므로 스택(Stack) 자료구조를 사용합니다.

 

ex) A에서 출발하여 E를 찾으시오.

 

1) A에서 첫 자식인 B를 탐색합니다. D, E에 접근이 가능합니다.

 

2) B의 첫 자식인 D를 탐색합니다. 추가로 접근 가능한 노드가 없습니다.

 

3) B의 두번째 자식인 E를 탐색합니다. 원하는 도착지를 찾아서 탐색을 종료합니다.

 

 

 

예시 문제

BFS와 DFS를 연습할 수 있는 가장 기본 문제는 아래 문제입니다.

백준 1260번 문제 : DFS와 BFS

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

 

이건 제가 Java로 푼 1260번 문제입니다.

https://naknak.tistory.com/128

BJ S2 1260 DFS와 BFS - Java