2021.11.13 코테_BFS 예시코드

2021.11.13 코테_BFS 예시코드

728x90

# 오늘의 문제

BFS ( Breadth-First Search) 예시코드

# BFS

너비우선 탐색 - 그래프 ( 간선과 노드로 이루어진) 라는 자료구조를 탐색하는 문제가 많이 출제된다. 거기에서 사용하는 알고리즘이라고 표현할 수 있겠다.

아래의 코드는 해당 그래프를 BFS 로 탐색하는 방법의 예시를 코드로 옮겨 놓은 것이고 이로써 직접 작성해보며 BFS 에 대한 이해를 높이기 위해 서술 해두었다.

from collections import deque def bfs(graph, start, visited): queue = deque([start]) visited[start] = True while queue: #이부분에 print(queue) 하면 이해가 쉽다. v = queue.popleft() print(v, end=' ') #이 부분이 큐를 활용해서 BFS를 구현하는 핵심이라 볼 수 있다. # [1] -> [1,2,3,8] 들어가면 1빼고 루프 2빼고 루프 for i in graph[v]: if not visited[i]: queue.append(i) visited[i] = True graph = [ [], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ] visited = [False] * 9 bfs(graph, 1, visited)

728x90

from http://meotlog.tistory.com/45 by ccl(A) rewrite - 2021-11-13 21:27:18