[알고리즘 마스터] 5. DFS (깊이 우선 탐색)

안녕하세요. 개발감자 박그냥입니다!🥔

오늘은 알고리즘 중 깊이우선 탐색 에 대해서 정리해보도록 하겠습니다.

1. DFS (깊이 우선 탐색)

• 기능 : 그래프 완전 탐색 기법 중 하나이다. 시작 노드에서 시작해 한 쪽 분기를 정해 최대 깊이까지 탐색 후 다른 쪽 분기를 탐색하는 알고리즘
• 특징 : 재귀 함수로 구현(Stack Overflow 주의) 되고, 스택 자료구조(LIFO) 이용된다. 
• 시간 복잡도 : O(V+E)  ->> V : 노드 수 E: 에지 수

 

2. DFS (깊이 우선 탐색)의 원리

인접 리스트를 기준으로 원리를 설명합니다.

한 번 방문한 노드는 다시 방문하지 않아 노드 방문 여부를 체크한 배열이 필요합니다.

구현할 때에는 스택보다는 스택 성질을 갖는 재귀함수로 많이 구현하게 됩니다.

아래의 사진에 있는 그래프와 인접 리스트를 기반으로 깊이 우선 탐색의 원리를 설명해보도록 하겠습니다.

1) 탐색을 시작할 노드를 정한 후에 사용할 자료 구조(노드 방문 여부 저장) 를 초기화합니다.

저는 노드 1을 기준 노드로 설정하여 스택에 넣었습니다.

 

2) 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노트를 다시 스택에 삽입합니다.

스택에서 빼주면서 탐색 순서에 추가해줍니다. 스택에 들어간 노드는 방문 리스트에 저장해줍니다.

쉽게 생각하면 가장 위에 것 빼고 탐색순서 추가하고 인접 노드 넣고 리스트에 추가하고 를 반복한다고 생각하면 좋을 것 같아요.

 

처음 노드 1을 꺼내고 탐색 순서에 1을 추가합니다.

1의 인접 노드인 2와 3을 순서대로 넣어줍니다. 넣으면서 방문 리스트에 표시도 해줍니다.

 

 

1의 인접 노드 2와 3 중에서 가장 위쪽에 위치한 3을 꺼내고 탐색 순서에 추가해줍니다. 

3의 인접 노드인 4를 스택에 넣어 줍니다. 넣으며 방문 리스트에 4를 추가해줍니다.

 

3) 스택 자료구조에 값이 없을 때까지 반복합니다.

 

 

3. DFS (깊이 우선 탐색) 응용 문제 유형

단절점, 단절선, 사이클 찾기, 위상 정렬 등이 있다고 합니다!

이는 직접 코딩 테스트를 풀어보면서 익히는 게 빠를 것 같습니다.

 

---

알고리즘을 공부하다보니, 재밌네요! 문제를 직접 풀어보면 더 재미있을 것 같습니다.

그럼 더 유익한 포스팅으로 돌아올게요. 개발감자였습니다!