[Python][이코테] DFS

DFS

DFS는 Depth-First Search

깊이 우선 탐색이라고 한다.

 

 

DFS는 왼쪽에 해당하는 이미지로

 

먼저 갈수있는 최대한으로 읽고 그다음 옆의 노드를 읽는 것이다.

 

위의 경우 

 

A B D E F C G H I J

 

순이 된다.

 

DFS에서는 표현 하는 방식이 두 가지가 있다.

• 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현하는 방식
• 인접 리스트(Adjacency List): 리스트로 그래프의 연결 관계를 표현하는 방식

위는 인접 행렬의 예시이다.

 

각 노드를 축에놓고 노드 간의 거리를 표에 값으로 표시한다.

 

이를 코드로 구현하면

 

# 5-6 DFS,BFS DFS

INF = 999999999

graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

print(graph)

이와 같다.

 

 

위는 인접 리스트의 이미지이고

 

이를 코드로 구현하면

 

graph2 = [[] for _ in range(3)]

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

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

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

print(graph2)

위와 같다.

 

 

위 두 방식의 차이점은

 

행렬 방식은 불필요한 데이터도 저장을 해야 한다.

 

예를 들어 노드가 몇 백개가 있다면 그걸 다 2차원 배열로 표기할 것인가? 불가능하다.

 

하지만 리스트 방식을 이용한다면 엣지가 있는, 즉 노드 간에 연결이 된 부분만 표기를 해주면 되기 때문에 불필요한 데이터의 저장을 막을 수 있다.

 

하지만 리스트의 경우 하나하나 확인해야 하기 때문에 속도가 느리다.

 

저장공간 활용 - 행렬 < 리스트

속도 - 행렬 > 리스트

 

예를 들어서 노드 1과 노드 7이 연결되어 있을 때 행렬은 graph[1][7]을 확인하면 되지만

 

리스트는 앞에서부터 차례대로 읽어서 1과 7을 찾을 때까지 읽어야 한다.

 

 

 

DFS의 처리과정은 스택을 이용하는데 동작 과정은 다음과 같다.

 

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

 

노드 1을 시작으로 설정하여 인접한 노드 중에 방문하지 않은 노드가 여러 개 일 때 낮은 순서부터 방문하면

 

1 → 2 → 7 → 6 → 8 → 3 → 4 → 5

순서로 순회하게 된다.

 

# 5-8 DFS,BFS 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)
    
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9

dfs(graph, 1, visited)