전 시간에는 트리와 그래프를 순회하여 알고리즘이 어떻게 작동하는지 알아보았습니다. 이번엔 직접 코드로 옮겨봅시다. BFS 소스코드 def BFS(start): visit = [] queue = [] queue.append(start) visit.append(start) while queue: now_node = queue.pop(0) print(now_node, end='') for i in range(7): if matrix[node][i] == 1 and not i in visit: queue.append(i) visit.append(i) BFS 방식으로 그래프를 순회하는 소스코드입니다. matrix는 1차시에서 만들어둔 그래프를 사용하시면 되겠습니다. 먼저, 매개변수로 시작 정점을 입력받습니다. 시..

전 시간에 보았던 이 그래프를 탐색하는 방법에 들어가기 전에, DFS와 BFS를 좀 더 쉽게 이해시켜줄 '이진 트리'를 DFS와 BFS로 탐색해봅시다. 트리 순회 - BFS 더 간단한 BFS먼저 보도록 하겠습니다. 시작 노드는 늘 그렇듯 1번입니다. BFS의 경우는 너비 우선 탐색이라는 이름에 걸맞게 현재 노드의 자식노드를 전부 행선지에 넣고, 다음 노드에서도 반복하는 방식인데요, 그림으로 한번 보겠습니다. 1번 노드를 방문합니다. 다음 행선지는 2와 3이 되겠네요. 2번 노드를 방문합니다. 마찬가지로 2의 자식인 4와 5를 행선지에 추가합니다. 3번 노드를 방문합니다. 3의 자식은 6과 7을 행선지에 추가합니다. 이후 순차적으로 방문합니다. 한 그림으로 정리하면 다음과 같습니다. 다음과 같이, 1-2-..

우선, DFS와 BFS는 그래프를 순회하는 알고리즘이기 때문에 이 게시글에선 위 그래프를 예제로 사용하겠습니다. 간단하게 알아보자면 DFS는 Depth First Search, 깊이 우선 탐색이며 BFS는 Breadth First Search, 너비 우선 탐색이라고 알아두시면 되겠습니다. 탐색을 하려면 일단 그래프를 각 정점(vertex, v)들의 연결 상태를 나타내는 이중리스트(matrix)로 정의해야합니다. 매트릭스는 위와 같이 생겼습니다. 정점들의 연결상태를 우선 파란 칸(연결됨), 빨간 칸(연결되지 않음)으로 나누어 색칠하겠습니다. 먼저 자신이 자신과 연결되어있진 않으니 자신과 만나는 쌍을 전부 빨간색으로 색칠합니다. 다음은 이어진 점들의 쌍을 파란색으로 색칠합니다. 단, 간선의 방향이 없는 그래..