본문 바로가기

코딩테스트/알고리즘2

(알고리즘)DFS(Depth-First-Search) 깊이 우선 탐색 - 파이썬 DFS 1. DFS동작 예시 DFS(Depth-First-Search)는 말 그대로 깊은 곳에 있는 노드를 탐색하는 방법이다. DFS는 재귀함수를 사용하여 깊이 있는노드를 탐색한다. *재귀함수는 스택과 유사하다. 집어 넣은 순서대로 1->2->4->8->5->3->6->7 2. DFS코드 예제(python) import graphlib graph=[ [], #노드가 1부터 시작하므로 비움. [2,5,3], #1과 인접한 노드 [1,4,8], #2와 인접한 노드 [1,6,7], #3과 인접한 노드 [2], #4와 인접한 노드 [1,8], #5와 인접한 노드 [3,7], #6과 인접한 노드 [3,6], #7과 인접한 노드 [2,5] #8과 인접한 노드 ] visited = [False]*len(graph) .. 2021. 6. 11.
(알고리즘)BFS(Breadth-First-Search) 너비 우선 탐색 - 파이썬 + 백준 2178 풀이 BFS 1. BFS동작 예시 - 가까운 노드부터 우선적으로 탐색하는 알고리즘 - BFS는 큐를 사용하여 너비 우선으로 탐색한다. 집어 넣은 순서대로 1 -> 2 -> 3 -> 5 -> 4 -> 8 -> 6 -> 7 2. BFS 코드 예시 from collections import deque #queue를 사용하기 위해 쓰임 리스트를 사용해도 되지만, #deque이 시간을 더 단축해줌. def bfs(graph, start, visited): queue = deque([start]) #처음 정점을 넣어줌 visited[start] = True while queue: v = queue.popleft() print(v, end=' ') # 한 줄로 출력 for i in graph[v]: #만약 v=1일때 i는.. 2021. 6. 10.

티스토리툴바