TIL Day 21.

BFS (Breadth-First Search)

가까운 관계부터 우선적으로 탐색하는 알고리즘

deque 이용해서 풀기

# 함수 생성

def 연결된점찾기(점):
	#주어진 점과 연결된 점을 찾아서 return
    연결된점들 = 네트워크[점]
    
    for 연결된점 in 연결된점들:
    	if 연결된점 in 방문한점들:
        	연결된점들.remove(연결된점)
            
    return 연결된점들

def 점에대해액션하기(점):
	#해당 점을 방문한 것 체크
    방문한점들.append(점)
    
# 문제 풀기

queue = deque([1])

while queue: # 큐에 남아있는 점이 있다면
	점 = queue.popleft() #큐에서 점 빼기
    
    점에대해액션하기(점)
    
    다음점들 = 연결된점찾기(점)
    
    for 다음점 in 다음점들:
    	queue.append(다음점) # 큐에 찾아낸 연결된 점들 넣기
	

BFS의 장점

1. 최단 경로 찾기 가능 (가중치 없는 그래프)
2. 무한에 가까운 깊이를 가진 그래프 탐색이 가능
3. 코드 실행이 직관적이다

BFS의 단점

1. DFS에 비해 메모리를 많이 사용 (queue에 넣어놓아야 하기 때문)
2. 동작 검증이 DFS에 비해 까다롭다. 어떤 과정을 거쳤는지 알기 어려울 수 있음
3. 간선에 가중치가 있는 경우 최단 경로 구하기 X

⭐️ DFS, BFS 둘 다 탐색 알고리즘 이기 때문에 경로탐색, 네트워크, 조합만들기에서 모두 사용 가능

• BFS가 유리한 것: 최단 경로 전염,전이

알고리즘 문제 풀기

풀이 

스쿼드 공부방

BFS
바이러스
유기농배추