[05DFS/BFS] 5-6 DFS (p134~p143)

[DFS]

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

 

[그래프]

• 그래프는 노도(Node)와 간선(Edge)로 표현되며, 이때 노드를 정점(Vertex)라고도 함.
• 그래프 탐색이란, 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다.
• 두 노드가 간선으로 연결되어 있다면, '두 노드는 인접하다(Adjacent)'라고 표현

 

[인접 행렬 예제]

• 인접 행렬(Adjacency Matrix) 방식은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식.
• 연결이 되어있지 않은 노드끼리는 무한(Infinity)의 비용으로 봄.
  

  

INF = 999999999

# 2차원 리스트를 이용해 인접 행렬 표현
graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

print(graph)

 

 

[인접 리스트 예제]

• 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장.
• 인접 리스트는 '연결 리스트'라는 자료구조 이용.
• 
  

  

#행(Row)이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)]

#노드 0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1, 7))
graph[0].append((2, 5))

#노드 1에 연결된 노드 정보 저장(노드, 거리)
graph[1].append((0, 7))

#노드 2에 연결된 노드 정보 저장(노드, 거리)
graph[2].append((0, 5))

print(graph)

 

[인접 행렬 Vs 인접 리스트]

• 인접 행렬: 모든 관계를 저장하므로 노드 개수가 많을 수록 메모리가 불필요하게 낭비.
• 인접 리스트: 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용.
• 인접 리스트 방식은 연결된 데이터를 하나씩 확인해야하기 떄문에 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느림. 

 

[DFS의 동작 과정]

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노다가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
4. cf) '방문 처리'는 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미함. 각 노드를 한 번씩만 처리하기 위함.

 

[DFS의 탐색과정 시각화]

 

• 인접한 노드 중 방문하지 않은 노드가 여러 개 있으면 번호가 낮은 순서부터 처리한다.

 

 

• 노드의 탐색 순서(스택에 들어간 순서): 1 - 2 - 7 - 6 - 8 - 3 - 4 - 5

[DFS 소스코드]

#DFS 메서드 정의
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차원 리스트)
visited = [False] * 9

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