탐색 알고리즘2 BFS (Breadth First Search) 너비 우선 탐색 설명 BFS는 DFS와 같이 탐색을 주로하는 알고리즘입니다.이와 관련한 설명은 DFS 설명할 때 같이 했으니 보고오시는 것을 추천드립니다.https://ris-blog.tistory.com/22 DFS (Depth First Search) 깊이 우선 탐색 설명DFS는 우선 제목에 나와있듯이 '탐색'하는 알고리즘입니다.고로 이는 순서가 있는 혹은 방향이 있는 자료구조에서 쓰이며이는 선형 자료구조라고 합니다. 우선 DFS의 탐색 과정을 봅시다.위의 사ris-blog.tistory.com 바로 BFS의 작동 순서를 표시하겠습니다.노드 안의 숫자는 순서를 나타냅니다.이 그림에서 DFS와 BFS의 차이가 나타납니다.DFS는 하나의 노드를 끝까지 탐색한다면 BFS는 각 노드를 한번씩 탐색합니다.이해를 돕기위해 예를 들자.. 2024. 11. 2. DFS (Depth First Search) 깊이 우선 탐색 설명 DFS는 우선 제목에 나와있듯이 '탐색'하는 알고리즘입니다.고로 이는 순서가 있는 혹은 방향이 있는 자료구조에서 쓰이며이는 선형 자료구조라고 합니다. 우선 DFS의 탐색 과정을 봅시다.위의 사진은 DFS의 작동 순서를 매우 간단히 표현한 그래프입니다.화살표를 신경쓰기보다는 노드의 숫자를 보시면 좋습니다.노드의 숫자는 순서를 의미합니다. 고로 DFS의 원리를 정리하자면연결된 노드들 중 하나를 골라 그 노드에서 계속 탐색하고 탐색되지 않은 노드는 따로 처리하는 것입니다. 이를 코드로 구현하면 아래처럼 됩니다.*코드에서는 연결요소(connected component)를 구합니다.주석 On, m = map(int ,input().split()) # n : node, m = 간선visited = []graph =.. 2024. 11. 2. 이전 1 다음
