[알고리즘] DFS 개념 정리 / 문제 풀이

그래프를 깊은 곳 먼저 탐색하기

 

 

그래프 표현하는 법

1. 인접 행렬 -> 이차원 배열

 

2. 인접 리스트  -> 파이썬은 기본적으로 리스트에 append가 있어서 list를 사용하면 됨.

 

무엇을 쓰지? 

1. 메모리 측면

    list > 행렬

 

2. 속도 측면 

    행렬 > list

 

 

DFS로 풀 수 있는 문제들은 다음과 같은 특징을 갖는다.

1. 경로의 특징을 저장해둬야 하는 문제

 

필요한 세팅

1. 노드들을 넣을 스택 ( 파이썬에서는 리스트 )

2. visited 행렬 ( n x n  :  방향이 있는 그래프 ) / ( 리스트 : 방향 없는 그래프 )

 

구현할 때는 다음의 절차를 따른다. 

1. 시작 노드를 스택에 삽입 후 Visited 처리
2. 스택의 맨 위 노드의 인접 노드를 확인 => 인접 노드가 not visied 면 스택에 넣고 visited 처리
3. 인접 노드가 없거나 모두 visited면 스택의 맨 위 노드 꺼내기
4. 스택이 빌 때까지 2~4까지의 과정을 반복

 

시간 복잡도

O(N)