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

프로그래머스 Level2 문제인 N-Queen 를 풀려다가.. 백트래킹이 뭔지.. DFS가 무엇인지를 모르니 다른 사람들이 풀어 놓은 해설을 보더라도 전혀 이해가 가지 않았다.. 그래서 작성하게 된.. DFS..그럼 시작..

 

(DFS 정리는 나동빈님의 알고리즘 강의를 참고하여 작성되었습니다!)

(나동빈님의 유튜브 채널 :https://www.youtube.com/c/dongbinna)

 

DFS(Depth-Fist Search) 깊이 우선 탐색

- DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

- DFS는 스택 자료구조(또는 재귀 함수)를 이용하며, 구체적으로 다음과 같이 작동한다

1.  탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 꺼낸다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

 

예시) 예시 자료는 나동빈님의 알고리즘 강의를 참고하였다!

조건

 - 시작 노드 : 1

 - 방문 기준 : 번호가 낮은 인접 노드 부터

 

조건을 바탕으로 하여 DFS는 다음과 같이 작동한다.

1. 시작 노드 1번에서 시작하여 번호가 낮은 노드인 2번으로 이동한다.
2. 2번과 연결된 노드가 7번 밖에 없으므로 7번으로 이동한다
3. 7번 노드와 연결된 노드는 8번과 6번인데, 번호가 낮은 인접 노드부터 이동하므로 6번으로 이동한다.
4. 6번 노드와 연결된 노드가 없으니, 최상단 노드인 6번을 꺼낸다.
5. 다시 7번 노드로 돌아와 8번 노드를 방문한다.
6. 위와 같은 과정을 반복하여 나머지 노드 3,4,5 번을 반복한다.
7. DFS가 방문하는 순서를 정리하면 1번 >> 2번 >> 7번 >> 6번 >> 7번 >> 8번 >> 1번 >> 3번 >> 4번 >> 5번 이다.

 

위의 그래프와 과정을 코드로  구현한 것이다.

def dfs(graph, v, visited):
	# 현재 노드를 방문 처리
    visited[v] = True
    print(v, end = ' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)

# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]]
    
# 각 노드가 방문된 정보를 표현(1차원 리스트)
# 0번 인덱스를 사용하지 않기 위해 8이 아닌 9을 곱하여 리스트를 만든다
visited = [False] * 9


# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

각 세부 사항에 대한 코드를 아직도 이해하는 중이라 세세한 설명을 하기는 어렵지만, n-queens 의 스노우볼 덕분에 dfs와 백트래킹에 대한 전반적인 이해를 다질 수 있었다. n-queens 를 완벽하게 이해가 되는 날이 오기를 바라면서...

DFS에 대한 내용을 마친다..

 

(본 포스팅에 대한 문제가 있을 시, 바로 삭제하겠습니다!)