알고리즘 기본기 다지기9. 그래프 알고리즘 (DFS, BFS)

깊이우선탐색(DFS, Depth First Search)

그래프는 풍부한 표현력을 바탕으로 한 다양한 문제를 포함하며 이에 대한 해결 알고리즘 역시 다양하다. 순회(Graph traversal)란 그래프 내 모든 정점과 간선을 검사하는 절차를 말한다. 대표적인 그래프 순회인 DFS을 알아보자.

DFS는 이진 트리에 대한 선위순회와 유사한 양식으로 순회를 진행한다. 출발 정점으로부터 시작하여 출발정점에서 멀어지는 방향으로 진행한다.

DFS는 대표적인 미로문제 해결 제시안이다.

 

너비우선탐색(BFS, Breadth First Search)

BFS는 그래프를 순회하기 위한 일반적인 기법이다. 너비우선탐색은 이진트리에 대한 레벨순회와 유사한 양식으로 순회를 진행한다. 출발 정점으로부터 시작하여 간선을 따라 정점과 간선들을 방문하는 순서가 레벨순회에서와 마찬가지로 출발 정점에서 레벨 단위로 멀어지는 방향으로 진행한다.

DFS/BFS 연습문제

DFS/BFS는 그래프를 완전 탐색하는 알고리즘이다. 대부분의 문제는 서로 호환하여 해결할 수 있다. 문제를 풀면서 해당 문제에서는 어느쪽이 더 효율적인지 판단하는 능력을 길러야한다.

백준

1260(DFS와 BFS) 2178(미로탐색) 2667(단지번호 붙이기) 1012(유기농 배추) 7576(토마토) 1697(숨바꼭질) 4963(섬의 개수) 1987(알파벳) 7569(토마토) 2583(영역 구하기) 10451(순열 사이클) 2636(치즈) 1963(소수 경로) 16964(DFS 스페션 져지)

Leetcode

98(Validate Binary Search Tree)  99(Recover Binary Search Tree) 112(Path Sum) 113(Path Sum II) 437(Path Sum III) 113(Path Sum II)114(Flatten Binary Tree to Linked List) 116(Popularting Next Right Pointers in Each Node) 117(Popularting Next Right Pointers in Each Node)  1254(Count Vowel Strings) 1448 (Count Good Nodes in Binary Tree)

 

참고

백준 온라인저지  https://www.acmicpc.net/

LeetCode https://leetcode.com/ , https://leetcode.com/tag/depth-first-search/

위키백과(소수) https://ko.wikipedia.org/ 

 

문제 풀이

Github https://github.com/cri-kim/BlogPractice