코딩테스트/알고리즘
DFS/BFS
대표적인 그래프 탐색 알고리즘 DFS Depth-First Search 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이며, 스택 자료구조나 재귀 함수를 이용한다. 탐색 시작 노드로 재귀함수를 호출해 방문 처리한다. 현재 방문 노드에서 방문하지 않은 인접 노드가 하나라도 있으면 그 노드로 재귀함수를 호출해 방문 처리한다. 방문하지 않은 인접 노드가 없으면 해당 재귀 함수는 종료된다. 더 이상 2 - 3번의 과정을 수행할 수 없을 때까지 반복한다. # 재귀함수로 구현한 DFS def dfs(graph, v, visited): # 현재 노드를 방문 처리 visited[v] = True print(v, end=' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in g..
