깊이 우선 탐색
-
[그래프] DFS와 BFS 구현하기 :: 마이구미알고리즘 2017. 1. 19. 22:15
이번 글은 자료구조 중 그래프를 다뤄본다.백준 알고리즘 1260번을 통해 진행하니 참고하길바란다. 그래프는 정점과 간선으로 이루어진 자료구조의 일종이다. G = (V, E) 그림을 보다시피, 정점과 간선이 무엇을 나타내는 지 알 수 있다.정점은 각 출발점 도착점과 같은 점이라고 보면 되고, 간선은 그 정점간 연결된 관계를 뜻한다. 무방향 그래프와 방향 그래프가 있다.말그대로 방향이 있는 그래프는 2->1로만 갈 수 있고, 무방향이라면 2->1, 1->2 가능하다는 것이다.여기서는 무방향 그래프를 기준으로 다뤄볼 것이다. 그래프의 탐색에 있어 DFS, BFS 방식이 있다.깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 2가지 방식을 알아보자.두 탐색은 모든 정점을 한번만 방문한다는 같은 목표를 가지고 ..