DFS, BFS 개념 정리 및 구현

파이썬 알고리즘 인터뷰의 그래프 장에서의 DFS, BFS의 개념 정리 및 구현을 진행하여 그래프에 대한 전반적인 이해를 할 수 있도록 한다. 그래프 표현 방법 크게 인접 행렬(Adjacency Matrix) 방식과 인접 리스트(Adjacency List) 방식이 있는데 인접 리스트 방식으로 구현을 진행한다. 다음과 같은 graph가 있을 경우 python의 코드상의 구현은 다음과 같다. GRAPH = { 1: [2, 3, 4], 2: [5], 3: [], 4: [], 5: [6, 7], 6: [], 7: [3] } 위와 같이 딕셔너리와 리스트의 조합으로 인접 리스트 방식 그래프를 표현할 수 있다. DFS(Depth First Search) DFS는 깊이 우선 탐색으로 재귀함수 또는 스택을 사용하여 구현한..

2024.02.03