Dev_from the Bottom

BFS : Breadth-First-Search 너비 우선 탐색 가까운 노드부터 탐색하는 알고리즘 선입선출 방식인 Que 자료구조를 이용하는 것이 정석 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행함 알고리즘 동작 방식 1) 탐색 시작 노드를 Que에 삽입하고 방문 처리를 한다. 2) Que에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 Que에 삽입하고 방문 처리를 한다. 3) 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. BFS는 Que 자료구조에 기초한다는 점에서 구현이 간단 파이썬에서는 deque 라이브러리를 사용하는 것이 좋으며 탐색을 수행함에 있어 O(N)의 시간이 소요..

DFS : Depth-First-Search 깊이 우선 탐색 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘 동작 과정 1) 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2) 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3) 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. * 방문 처리 : 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미. 방문 처리를 함으로써 각 노드를 한 번씩만 처리 가능 ** DFS의..

DFS, BFS를 공부하기 전에 먼저 그래프(Graph)의 기본 구조를 알아야 함 그래프(Graph)의 기본 구조 그래프는 노드(Node)와 간선(Edge)로 표현됨 Node를 정점(Vertex)라고도 함 그래프 탐색 : 하나의 노드를 시작으로 다수의 노드를 방문하는 것 두 노드가 간선으로 연결되어 있다면, '두 노드는 인접하다(Adjacent)'라고 표현 '노드 : 도시, 간선 : 도로' 로 이해할 수 있음 Edge는 거리로 표현할 수 있는 '비용'을 갖을 수 있다. 인접 행렬, 인접 리스트 프로그래밍에서 그래프는 크게 2가지 방식으로 표현될 수 있음 1) 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 2) 인접 리스트(Adjacency List) : ..