[Graph] DFS (깊이 우선 탐색)

완전 탐색 방법으로 가장 깊은 바닥까지 갔다가, 해당 경로가 종료될 경우 마지막 갈림길로 돌아가 탐색을 반복한다. 이때, 마지막 갈림길로 돌아가는 행위를 위해 스택이 필요하다.

 

DFS

비선형 구조인 그래프를 빠짐없이 검색하는 방법(완전탐색). 깊이 우선 탐색과 너비 우선 탐색이 있다. 시작 정점의 한방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 막다른 길이면, 이전 갈림길로 돌아가 탐색을 진행한다. 마지막 갈림길로 돌아가는 행위를 하기 위해 후입 선출 구조인 스택을 사용한다.

 

개요

1. 시작정점 v를 결정하여 방문한다.
2. 정점 v에 인접한 정점 중에서
   1. 방문하지 않은 정점 w가 있다면, 정점 w를 스택에 push하고 정점 w를 방문한다. 그리고 w를 v로 하여 다시 위 순서를 반복한다.
   2. 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해서 스택을 pop 하여 가장 마지막에 방문한 정점을 v로 하여 다시 위 순서를 반복한다
3. 스택이 공백이 될 때까지 2번을 반복한다.

 

구현

✅ 반복문

stack 과 visited 에 방문할, 방문한 정점을 기록하여 모든 정점을 방문한다.

# 1. 입력 받기
V, E = map(int,input().split())
node = list(map(int,input().split()))

# 2. 인접행렬 만들기
matrix = [[ 0 for _ in range(V+1)] for _ in range(V+1)]
for i in range(E):
    matrix[node[i * 2]][node[i * 2 + 1]] = 1
    matrix[node[i * 2 + 1]][node[i * 2]] = 1

# 3. 스택과 visited 생성
stack = [1] # 방문할 정점 / 1에서 시작한다고 가정하자
visited = [0] * (V+1) # 방문한 정점
visited[1] = 1

# 4. 코드 구현
while stack:
    # 방문 할 정점에서 맨위 값을 빼고 방문하자, v는 현위치
    v = stack.pop()

    # 현재 정점 v에서 갈 수 있는 정점을 방문할 정점에 쌓자
    for i in range(1, V+1): # 0인덱스는 쿠션이라 1부터
        # 연결되어있고(해당값이 0이 아니고), 방문하지 않았으면
        if matrix[v][i] and not visited[i]:
            # 방문할 정점에 넣고 방문체크
            stack.append(i)
            visited[i] = 1

print(visited)

 

✅ 재귀

함수의 재귀호출을 통해 함수 호출 자체가 스택에 쌓이는 형태로 수행된다. 따라서 별도의 스택은 필요가 없고 가장 깊은 노드까지 쭉이어져 가다가 더 이상 연결된 노드가 없으면, 해당 함수의 호출이 스택에서 제거되고 가장 차상위에 있는 함수가 다시 실행된다.

def DFS_Recursive(v):
    visited[v] = 1
    for i in range(1, V+1):
        if matrix[v][i] and not visited[i]:
            DFS_Recursive(i)


# 1. 입력 받기
V, E = map(int,input().split())
node = list(map(int,input().split()))

# 2. 인접행렬 만들기
matrix = [[ 0 for _ in range(V+1)] for _ in range(V+1)]
for i in range(E):
    matrix[node[i * 2]][node[i * 2 + 1]] = 1
    matrix[node[i * 2 + 1]][node[i * 2]] = 1

visited = [0] * (V+1) # 방문한 정점

DFS_Recursive(1)
print(visited)

 

추가 설명

• DFS를 구현하기 위해서는 stack에 대해 먼저 학습하는 것이 좋다.
• 간단한 DFS 문제나, 가지의 갯수가 많지 않을때는 DFS를 단순한 형태로 구현하면 되지만 제한 시간이 타이트하거나 반복 횟수가 많은 경우 백트래킹이 반드시 필요하다. 때에 따라 DP로도 가지치기를 한다.
• 대표적인 알고리즘 문제라서 백준, 프로그래머스 등등 여러 코테 사이트에서 연습문제를 풀어 볼 수 있다.