DFS 와 BFS 에 대한 글은 아래 글을 참고한다. 2020/03/29 - [Algorithm] - 그래프 BFS, DFS 알고리즘 (with Python3) 그래프 BFS, DFS 알고리즘 (with Python3) 그래프 탐색 알고리즘에는 대표적으로 BFS 와 DFS 가 있다. 본 글에서는 아래 그래프를 가지고, BFS 와 DFS 의 탐색 알고리즘을 살펴본다. BFS 너비 우선 탐색을 BFS 라 부르고, Breadth Frist Search 의 약자이.. memostack.tistory.com 미로찾기 알고리즘 DFS, BFS 알고리즘을 이용해서 미로찾기 알고리즘을 구현할 수 있다. 문제 풀이의 핵심은 2가지이다. 미로 찾기 문제를 풀때는 미로를 모형화하여 그래프로 나타내는 것. 자료구조(Stack..

BFS 에 대한 개념은 아래 글을 참고한다. 2020/03/29 - [Algorithm] - 그래프 BFS, DFS 알고리즘 (with Python3) 탐색 알고리즘 BFS 응용 모든 노드를 탐색(방문)하면서 노드(Node)간의 비용(Cost)을 같이 구한다. 문제 사람들간의 친밀도를 구한다. 사람: 노드(Node) 친밀도: 비용(Cost) 예를들어, 사람과 사람 사이의 친밀도를 1 이라 한다. A ~ M 까지 사람이 있을때, A를 기준으로 각각의 사람들과의 친밀도를 구한다. A 와 B는 친밀도가 1이다. B 와 D는 친밀도가 1이다. A와 D는 친밀도가 2이다. ... Coding - Python3 본 글에서는 파이썬을 이용하여 문제를 풀이한다. BFS 알고리즘으로 노드를 탐색하는것은 동일하다. 단, ..

그래프 탐색 알고리즘에는 대표적으로 BFS 와 DFS 가 있다. 본 글에서는 아래 그래프를 가지고, BFS 와 DFS 의 탐색 알고리즘을 살펴본다. BFS 너비 우선 탐색을 BFS라 부르고, Breadth Frist Search 의 약자이다. 해당 노드와 같은 레벨(Level)의 노드를 먼저 탐색을 하기 때문에 붙여진 이름이다. 위 그래프를 예로 탐색 순서를 나열하면, 아래와 같은 순서로 탐색을 하게된다. A - B - C - D - E - F - G - H - I - J - K - L - M 코드 아래 코드는 unittest 기반으로 작성했다. 알고리즘은 bfs() 메소드를 참고한다. # -*- coding: utf-8 -*- import unittest def bfs(graph, start): """..