포시코딩

BFS 알고리즘 구현 큐 자료구조 활용 need_visit queue visited queue 개념 위 그래프에 대해 BFS를 구현한다면 다음과 같은 순서로 진행된다. 1. 제일 처음 노드 A를 need_visit queue에 추가한다. (시작) 2. need_visit queue에서 dequeue 한 뒤 temp_node로 가져온다. (코드에선 list를 사용하기 때문에 pop(0)을 통해 dequeue했다.) 3. temp_node가 visited queue에 존재하는지 확인 4-1. 없다면 visited queue에 A를 추가 4-2. 존재한다면 아무것도 하지 않고 2번부터 다시 시작 5. temp_node였던 A를 graph_dict에서 key로 찾아 나온 value를 need_visit queu..

개요 대표적인 그래프 탐색 알고리즘 너비 우선 탐색(Breadth First Search:BFS) 정점들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 탐색하는 방식 깊이 우선 탐색(Depth First Search:DFS) 정점의 자식들을 먼저 탐색하는 방식 예제 BFS 방식: A - B - C - D - G - H - I - E - F - J * 한 단계씩 내려가면서, 해당 노드와 같은 레벨에 있는 노드들(형제 노드들)을 먼저 순회한다. DFS 방식: A - B - D - E - F - C - G - H - I - J * 한 노드의 자식을 타고 끝까지 순회한 후, 다시 돌아와서 다른 형제들의 자식을 타고 내려가며 순회한다. 구현 파이썬에서는 딕셔너리와 리스트 자료 구조를 활용해 그래프를 표현할 수 ..

BFS란? 한 노드를 시작으로 인접한 모든 노드들을 우선 방문하는 방법. 더 이상 방문하지 않은 노드가 없을 때까지 방문하지 않은 모든 노드들에 대해서도 BFS를 적용한다. BFS 구현 방법 1. 큐 BFS는 현재 인접한 노드들을 먼저 방문해야 한다. 이걸 다시 말하면 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고 가장 처음에 넣은 노드를 꺼내서 탐색하면 된다. -> 처음에 넣은 노드를 꺼낸다. -> 큐를 쓰면 되겠구나 큐를 사용한다는 점 말고는 DFS에서 스택을 사용하는 방법과 매우 유사하다. 코드로 직접 살펴보자 graph = { 1: [2, 3, 4], 2: [1, 5], 3: [1, 6, 7], 4: [1, 8], 5: [2, 9], 6: [3, 10], 7: [3], 8: [4], 9:..