알고리즘
-
너비 우선 탐색(BFS, Breadth First Search)알고리즘 2023. 10. 29. 12:04
너비 우선 탐색? 어떤 노드를 방문하여 확인한 후, 목표한 노드가 아니면 그 노드와 연결된 정점들 중에서 우선 순위가 동일한 다른 노드를 찾고 그 순위에 없으면 그 다음 순위 노드를 차례대로 찾는 방법 즉, 깊게 탐색하기 전 넓게 탐색하는 방법이다. * 두 노드의 최단 경로를 찾고 싶은 경우에 이 방법을 선택 * BFS보다 복잡하다. 구현 방법 큐(Queue)를 사용한다. 문제 다음과 같이 입력이 주어질 때 너비 우선 탐색을 한 순서대로 노드의 인덱스를 공백 구분으로 출력하시오. 데이터 graph = {'E': ['D', 'A'], 'F': ['D'], 'A': ['E', 'C', 'B'], 'B': ['A'], 'C': ['A'], 'D': ['E','F']} 출력 E D A F C B 문제 풀이 가까..
-
깊이 우선 탐색(DFS, Depth First Search)알고리즘 2023. 10. 29. 11:43
깊이 우선 탐색? 목표한 노드를 찾기 위해 가장 우선 순위가 높은 노드의 자식으로 깊이 들어갔다가 목표 노드가 존재하지 않으면 처음 방문한 노드와 연결된 다른 노드부터 그 자식 노드로 파고드는 검색 방법 * 모든 노드를 방문하고자 하는 경우에 이 방법을 선택 * BFS보다 좀 더 간단하지만, 단순 검색 속도 자체는 느리다. 구현 방법 스택을 사용한다. 문제 다음과 같이 리스트 형태로 노드들의 연결 관계가 주어진다고 할 때 깊이 우선 탐색으로 이 노드들을 탐색했을 때의 순서를 공백으로 구분하여 출력하세요. graph = {'E': ['D', 'A'], 'F': ['D'], 'A': ['E', 'C', 'B'], 'B': ['A'], 'C': ['A'], 'D': ['E','F']} 사진 도식화 문제풀이 현..