탐색 알고리즘 DFS

깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
최상단 노드에서 갈 수 있는 노드가 있다면 크기가 낮은 방향으로 들어가고, 그 노드가 다시 최상단 노드가 되고 이런 방식으로 진행

• 스택과 같이 마지막에 들어온 놈을 빼주는 식
• 그래프, 노드, 방문처리 필요

Graph 표현 방식

1. 인접 행렬

# 인접 행렬
graph = [
		[0, 7, 5],
        [7, 0, INF],
        [5, INF, 0]
        ]

2. 인접리스트

# 인접 리스트
[[(1,7), (2,5)], [(0,7)], [(0, 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)
    
graph = [ 
         [],
         [2,3],
         [1],
         [1,4],
         [3,4]]

visited = [False] * 5

dfs(graph, 1, visited)

• 풀이 메뉴얼 정돈 암기 해주자

1. Input - Graph, 시작 Node, 방문 처리 리스트
2. 방문 처리 안됐으면 탐색하는 식
3. 위의 경우 인접 리스트로 그래프를 표현함

DFS 풀이 - n과 m 시리즈

https://wikidocs.net/16038

• copy & deepcopy
• 문제점 : 같은 메모리를 리스트들이 참조해서 이상현상(?) 발생 , append를 하지 않았는데 같은 메모리를 참조해서 두 개의 리스트에 같이 append됌

시간복잡도

• O(N+V) - 노드 + 간선의 개수

탐색 알고리즘 BFS