BFS

Jin·2021년 6월 15일

목록 보기

2/2

BFS 개념

BFS

대기열에 다음에 방문할 노드를 담아놓기.

그래프에서 어떤 노드를 방문하면, 인접한 노드들을 다음에 방문할 노드로 대기열에 추가한다. 대기열에 있는 모든 노드들을 순회하면서, 다시 인접한 노드들을 만난 경우에 대기열에 추가한다.

대기열은 큐(Queue) 자료구조를 사용해서 구현할 수 있다. 선입선출 구조로 먼저 추가한 노드들을 먼저 방문하게 된다. 방문하는 과정에서 이미 방문했던 노드들을 다시 방문하는 경우가 생길 수도 있으므로, 그런일이 예상된다면, 어떤 노드들을 방문했는지를 기록하는 기록용 자료구조를 관리 할 필요가 있다.

큐가 비었을때 탐색이 종료된다. 대기열을 사용하여, 인접한 노드들을 모두 방문한 후에 다음 노드들을 방문하므로, 탐색이 종료되는 시점에서의 경로가 최단경로가 된다.

DFS 와의 차이

DFS 에서는 다음에 방문할 노드들을 담아놓는 자료구조로 대기열이 아닌 스택(Stack) 구조를 쓴다. 스택 구조를 활용하면, 가장 나중에 자료구조에 들어간 노드가 가장 먼저 나오게 된다. 따라서, 깊이 방향의 탐색을 계속하게 되고, 그래프를 가장 깊이 탐색한 이후에야 다음으로 넘어가게 된다.

BFS 개념 익히기

https://leetcode.com/problems/maximum-depth-of-n-ary-tree/

BFS 풀이

while 문으로 풀이

class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0
        
        q = []
        q.append(root)
        depth = 0
        while q:
            depth += 1
            for _ in range(len(q)):
                current = q.pop(0)
                for child in current.children:
                    q.append(child)
        return depth

DFS 풀이

재귀로 풀이

class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0
        def go(current = root, depth = 1):
            if not current.children:
                return depth
            return max(go(child, depth + 1) for child in current.children)
        return go()

BFS 문제풀이

게임 맵 최단거리

문제링크: https://programmers.co.kr/learn/courses/30/lessons/1844
풀이코드: https://github.com/gringrape/daily_coding_dojo/blob/main/20210614/python2/test_solution.py

효율성에서 실패한 이유

노드의 방문여부를 기록하는 로직의 위치가 잘못되었다.

처음에는 노드의 방문여부를 기록하는 로직을 노드를 실제로 방문하는 위치에 넣었다.

class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0
        
        q = []
        q.append(root)
        depth = 0
        while q:
            depth += 1
            for _ in range(len(q)):
                current = q.pop(0)    
            	mark_as_visited(current) # 여기에 넣음
                for child in current.children:
                	if not visited:
                    	q.append(child)
        return depth

노드를 방문으로 체크하지 않고 대기열에 넣다보니, 이미 방문한 노드의 자식들까지 대기열에 다시 추가되는 경우가 발생했다. 방문했는지 여부를 체크했기 때문에, 답은 올바르게 나왔지만, 대기열이 너무 많은 노드가 추가되게 되면서, 연산이 너무 많아져서 연산시간이 오래걸렸고, 효율성 검사에서 실패하게 되었다.

class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0
        
        q = []
        q.append(root)
        depth = 0
        while q:
            depth += 1
            for _ in range(len(q)):
                current = q.pop(0)
                for child in current.children:
                	if not visited:
                		mark_as_visited(child) # 여기에 넣으면 된다.
                    		q.append(child)
        return depth