BFS

BFS

최근 그래프 탐색에 대해 궁금해져서 BFS, DFS에 대해 정리해보고 싶어졌다. 일단 BFS부터 천천히 코드로 만들어가면서 진행해 볼 예정이다.

BFS는 너비 우선 탐색 기법으로 같은 레벨에 있는 노드부터 찾아가면서 탐색하는 기법이다. 예시로써 가져올 그래프 모양은 한 블로그를 참고했다.

Progress

코드를 쓰기 전에 과정부터 생각해보자. 정답은 A - B - C - H - D - I ... 이런 식으로 나와야 한다. 그러기 위해서는 인접한 노드를 알아야 한다. A는 B, B는 A, C, H 이렇게 연관짓는다.

생성할 때 부모 노드 -> 자식 노드 순서로 적는 것이 좋다. 자식 노드의 순서는 좌측이나 우측부터 해도 상관은 없지만 섞지는 않는다.

graph = {
	'A': ['B']
    'B': ['A', 'C', 'H']
    ...
}

이런 식으로 딕셔너리를 만들어준다. 이제 코드를 통해 작성해보자.

Code Review

graph = {
    'A': ['B'],
    'B': ['A', 'C', 'D'],
    'C': ['B', 'E', 'F'],
    'D': ['B', 'G', 'H', 'I'],
    'E': ['C'],
    'F': ['C'],
    'G': ['D'],
    'H': ['D'],
    'I': ['D']
}

def bfs(graph, start_node):
	visited = []
    started = []
    
   	started.append(start_node)
    
    while started:
    	last_node = started.pop(0)
        
        if last_node not in visited:
        	visited.append(last_node)
            started.extend(graph[node])
            
    retun visited

코드에 대한 설명을 하면 다음과 같다.

1. 방문한 노드의 리스트와 큐의 역할을 해주는 리스트를 만든다. 처음에 받는 파라미터가 첫 방문 노드이기 때문에 append 해준다.
2. 이제 started 리스트가 비지 않으면 무한 루프를 태워주는 로직을 생성한다.
3. 큐의 역할을 수행해주는 리스트에서 앞의 값을 하나 빼준다. 방문했던 적이 있는지 확인해야하기 때문이다.
4. 방문했다면 다음 노드를 확인하도록 한다.
5. 방문하지 않았다면 방문한 리스트에 append한다.
6. 인접한 노드를 딕셔너리로 만들었기 때문에 부모 노드는 대부분 visited 리스트에 들어갔을 것이고 자식 노드들은 대부분 없을 것이기에 순차적으로 쌓이게 될 것이다.

다음에는 BFS를 통한 예제 풀이를 진행하겠다.

Reference Blog

https://itholic.github.io/python-bfs-dfs/