DFS 이론 정리

분류

Graph와 Tree의 구분은 Cycle이 생기냐 마냐의 차이이다. Tree는 Graph에 속한다.

DFS는 크게 정보정리와 로직으로 구분된다.

정보정리

1. 인접행렬을 사용하여 자료구조를 (Tree 혹은 Graph) 표현(정보정리)

2. 인접 리스트를 사용하여 자료구조를 (Tree 혹은 Graph) 표현(정보정리)

로직

1. 스택을 활용한 풀이

2. 재귀함수를 활용한 풀이

따라서 4가지 경우의 수로 DFS를 풀 수 있다.

어떤 방식이 우월하다 하는 것은 없고, 많이 사용되는 방식은 인접행렬-스택 or 인접리스트-스택 방식이다.(이게 재귀보다 빠르기 때문) 

다만 더 어려운 문제풀이의 경우 재귀방식이 사용된다.(ex) Segment Tree)

양방향 입력 예시

7 8  # Vertex = 7개, Edge = 8개인 그래프가 있을 때,
1 2  # 다음 8개의 줄에 연결 정보를 제공
1 3
2 4
2 5
4 6
5 6
6 7
3 7

인접 행렬로 정리하기 - 나중에 edge별 가중치 추가해줄 때 유리함

V, E = map(int, input().split())  # Vertex(포도알), Edge(선) 갯수

adj_matrix = [[0] * (V + 1) for _ in range(V + 1)]  # 인접행렬 기본틀 + 0번 포도알은 안씀

for _ in range(E):  # 간선 갯수만큼 돌면서 연결 정보를 받음
    start, end = map(int, input().split())  # 시작점과 끝점
    adj_matrix[start][end] = 1
    adj_matrix[end][start] = 1  # 양방향 그래프니까!!

# adj_matrix print 결과

# [[0, 0, 0, 0, 0, 0, 0, 0],  => 0번 포도알은 존재하지 않음
#  [0, 0, 1, 1, 0, 0, 0, 0],  => 1번 포도알은 2, 3번으로 갈 수 있음
#  [0, 1, 0, 0, 1, 1, 0, 0],  => 2번 포도알은 1, 4, 5번 가능
#  [0, 1, 0, 0, 0, 0, 0, 1],  => 3번 포도알은 1, 7번 가능
#  [0, 0, 1, 0, 0, 0, 1, 0],  => 4번 포도알은 2, 6번 가능
#  [0, 0, 1, 0, 0, 0, 1, 0],  => 5번 포도알은 2, 6번 가능
#  [0, 0, 0, 0, 1, 1, 0, 1],  => 6번 포도알은 4, 5, 7번 가능
#  [0, 0, 0, 1, 0, 0, 1, 0]]  => 7번 포도알은 3, 6번 가능

인접 리스트로 정리하기 -  공간복잡도가 낮다는 장점

V, E = map(int, input().split())

adj_list = [[] for _ in range(V + 1)]

for _ in range(E):
    start, end = map(int, input().split())
    adj_list[start].append(end)
    adj_list[end].append(start)  # 양방향

# adj_list = [[], [2, 3], [1, 4, 5], [1, 7], [2, 6], [2, 6], [4, 5, 7], [6, 3]]

스택 + 인접행렬 - 공간 복잡도 높으나, 단방향 그래프인 경우 전치로 방향 전환 유리함

V, E = map(int, input().split())  # Vertex, Edge 갯수

adj_matrix = [[0] * (V + 1) for _ in range(V + 1)]  # 인접행렬 기본틀

for _ in range(E):  # 간선 갯수만큼 돌면서 연결 정보를 받음
    start, end = map(int, input().split())  # 시작점과 끝점
    adj_matrix[start][end] = 1
    adj_matrix[end][start] = 1  # 양방향 그래프니까!!

stack = [1]  # 맨처음 시작점은 1번 포도알
visited = []  # 궤적 기록용

while stack:  # 스택이 빌때까지 돌아라!
    current = stack.pop()  # 우선 스택에서 현재 위치 하나 뽑고
    if current not in visited:  # 방문하지 않은 곳이라면,
        visited.append(current)  # 방문했다고 체크해줌
		
		# 위의 if문 안으로 넣으면 더 좋습니다.
    for destination in range(V+1):  # current 입장에서 어디로 갈 수 있는지 모조리 체크
        if adj_matrix[current][destination] and destination not in visited:  # 갈수있고 + 방문 안했으면!
            stack.append(destination)  # 다음 갈 곳으로 Stack에 저장

print('이동경로:', *visited)

# 이동경로: 1 3 7 6 5 2 4

스택 + 인접 리스트 - 공간복잡도가 낮다는 장점

V, E = map(int, input().split())  # Vertex, Edge 갯수

adj_list = [[] for _ in range(V + 1)]  # 인접리스트 기본틀

for _ in range(E):  # 간선 갯수만큼 돌면서 연결 정보를 받음
    start, end = map(int, input().split())  # 시작점과 끝점
    adj_list[start].append(end)
    adj_list[end].append(start)  # 양방향 그래프니까!!

stack = [1]  # 맨처음 시작점은 1번 포도알
visited = []  # 궤적 기록용

while stack:  # 스택이 빌때까지 돌아라!
    current = stack.pop()  # 우선 스택에서 현재 위치 하나 뽑고
    if current not in visited:  # 방문하지 않은 곳이라면,
        visited.append(current)  # 방문했다고 체크해줌

    for destination in adj_list[current]:
        if destination not in visited:  # 갈 수 있고 + 방문 안했으면!
            stack.append(destination)  # 다음 갈 곳으로 Stack에 저장

print('이동경로:', *visited)

# 이동경로: 1 3 7 6 5 2 4

재귀 + 인접 리스트 - 가독성은 좋으나 재귀 자체가 좀 느림

재귀함수를 활용하는 경우 return을 쓰면 끊길 수 있으므로 조심해야 한다.

def dfs(n):
    if n not in visited:  # 우선 visited 없으면 넣어줌
        visited.append(n)

    for destination in range(V+1):
        if adj_matrix[n][destination] and destination not in visited:
            dfs(destination)  # 다음 재귀 깊이로 이동

V, E = map(int, input().split())  # Vertex, Edge 갯수

adj_matrix = [[0] * (V + 1) for _ in range(V + 1)]  # 인접행렬 기본틀

for _ in range(E):  # 간선 갯수만큼 돌면서 연결 정보를 받음
    start, end = map(int, input().split())  # 시작점과 끝점
    adj_matrix[start][end] = 1
    adj_matrix[end][start] = 1  # 양방향 그래프니까!!

visited = []  # 궤적 기록용

dfs(1)  # 1번 포도알부터 시작!

print('이동경로:', *visited)

# 이동경로: 1 2 4 6 5 7 3 => 이거 다른거 주의!!
# main이 종료되어야 sub가 실행된다는 것을 생각
# 다음 main은 이전 main의 sub임
# (main) (sub1) (sub2) ...
# 1
# 1-2 / 1-3
# 1-2-4 / 1-2-5 / 1-3
# 1-2-4-6 / 1-2-4-5 / 1-2-5 / 1-3
# 1-2-4-6-5 / 1-2-4-6-7 / 1-3 # main이 5를 갔으니 sub 1-2-5, sub 1-2-4-5는 시작도 못함
# (1-2-4-6-5) / 1-2-4-6-7 / 1-3 # main 종료 및 기록됨, 이전 main 1-2-4-6이 main이 됨
# (1-2-4-6-5)-7 / 1-3 # main이 7을 갔으니 sub 1-2-4-6-7은 시작도 못함
# (1-2-4-6-5)-7-3 # main이 3을 갔으니 sub 1-3은 시작도 못함
# main 종료, sub는 없음