[Algorithm]DFS/BFS 개념

틀린 부분이 있다면 언제든지 댓글 남겨주세요! 

---

DFS(Depth-First Search)

: 깊이를 우선적으로 탐색, 스택 및 재귀함수 사용

  최상단 노드를 시작으로 인접한 노드 중 방문하지 않은 노드를 깊이 우선으로 선택

  방문하지 않은 인접 노드가 없으면 스택의 최상단 노드를 꺼냄

  방문했던 노드를 체크하여 더 이상 방문할 수 있는 노드가 없는 경우 종료 

# chapter 5 DFS


def dfs(graphs, n, visit):
    visit[n]=True   # 방문
    #print(n)
    for i in graphs[n]:
        if visit[i]==0:
            visit[i]=1
            dfs(graphs, i, visit)
           
visit=[0]*9        # graph의 개수에 맞춰 노드 방문 여부 확인을 위한 리스트 생성
graphs=[
    # 첫번째 배열은 0번째 노드로, 노드 번호를 맞추기 위해 삽입
    [],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[6,8],[1,7]
]


dfs(graphs, 1, visit)

---

BFS(Breadth-First Search)

: 너비 즉 가까운 노드를 우선적으로 탐색, 큐를 이용하여 구현

  시작 노드를 처음 큐에 넣고 방문처리

  이후 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리

  위의 과정을 반복하고 더 이상 큐에 확인할 노드가 없으면 종료

 

# chapter5 BFS

from collections import deque

def bfs(start, graph, visit):
    queue=deque([start])    # 인접 노드 담은 스택
    visit[start]=1			# 방문처리
    
    while queue:			# 큐에 노드가 없을 때까지 반복
        now=queue.popleft()	# 큐의 맨 처음 저장된 노드 pop
        print(now)
        
        for i in graph[now]:	# pop한 노드와 인접한 노드 
            if visit[i]==0:		# 인접한 노드가 방문하지 않은 노드인 경우
                queue.append(i)	# queue에 해당 노드를 삽입하고
                visit[i]=1		# 방문처리
                
graph=[
    [], [2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]
]

visit=[0]*9

bfs(1, graph, visit)

 

 

 

 

출처: 이것이 코딩테스트다 나동빈 저