[Algorithm] DFS/BFS 코드 설명

1. DFS 알고리즘

1-1) DFS 알고리즘 구현 기본 코드

#DFS 메서드 정의
def dfs(graph, v, visited):
    # 현재 노드(v)를 방문 처리
    visited[v] = True
    print(v, end=' ') # 방문한 노드의 번호를 출력
    # 현재 노드(v)와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

#각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [
    [],
    [2, 3, 8], # 1번 노드와 연결된 노드
    [1, 7], # 2번 노드와 연결된 노드
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

#각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False]*9 
#0번 인덱스를 사용하지 않기 위해 요소를 9개로 설정
#False : 노드를 미방문한 상태

#정의된 DFS 함수 호출
dfs(graph, 1, visited)

1-2) DFS 알고리즘 작동 방식 설명

dfs(graph, 1, visited)

• graph = 노드가 연결된 정보 (2차원 리스트)
• 1 = 시작 노트
• visited = 노드가 방문된 정보 (1차원 리스트)
  
  

visited[1] = True
print(1, end = ' ')

visited = [False, False, False, False, False, False, False, False, False]
visited = [False, True, False, False, False, False, False, False, False]

1번 노드의 방문 정보를 visited list에 저장한다.

• False = 미방문
• True = 방문

for i in graph[i]:

graph[1] = [2, 3, 8]
1번 노드의 인접 노드인 [2, 3, 8]에 대하여 if문 작동

if not visited[i]:

노드의 방문 정보 리스트(visited list)에서 1번 노드의 인접 노드
visited[2], visited[3], visited[8] 가 False라면 즉, 미방문 상태라면 '노드를 방문하고 인접 노드를 방문해서 미방문/방문을 확인하는 dfs 함수'를 다시 반복한다.

-> 모든 노드를 방문 처리하게 된다.

---

2. BFS 알고리즘

2-1) BFS 알고리즘 구현 기본 코드

from collections import deque

#BFS 메서드 정의
def bfs(graph, start, visited):
    #큐(queue) 구현을 위한 deque 라이브러리 사용
    queue = deque([start])
    #현재 노드를 방문 처리
    visited[start] = True
    
    #큐가 빌 때까지 반복
    while queue:
        #큐에서 하나의 원소를 뽑아 출력(popleft = 제거)
        v = queue.popleft()
        print(v, end=' ')
        #해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

#각 노드와 연결된 정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [
    [],
    [2, 3, 8], # 1번 노드와 연결된 노드
    [1, 7], # 2번 노드와 연결된 노드
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False]*9 
# 0번 인덱스를 사용하지 않기 위해 요소를 9개로 설정
# False : 노드를 미방문한 상태

# 정의된 DFS 함수 호출
bfs(graph, 1, visited)

1-2) DFS 알고리즘 작동 방식 설명

bfs(graph, 1, visited)

• graph = 노드가 연결된 정보 (2차원 리스트)
• 1 = 시작 노트
• visited = 노드가 방문된 정보 (1차원 리스트)
  
  

queue = deque([1])

deque는 스택과 큐의 기능을 모두 가진 객체
queue라는 이름으로 deque 객체 리스트 [1]을 생성한다.

visited[1] = True

visited = [False, False, False, False, False, False, False, False, False]
visited = [False, True, False, False, False, False, False, False, False]

1번 노드의 방문 정보를 visited list에 저장한다.

• False = 미방문
• True = 방문
  
  

while queue:
	#큐에서 하나의 원소를 뽑아 출력(popleft = 제거)
    v = queue.popleft()
    print(v, end=' ')
    #해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
    for i in graph[v]:
        if not visited[i]:
            queue.append(i)
            visited[i] = True

큐 리스트가 모두 빌 때까지 다음의 과정을 반복한다.

#큐에서 하나의 원소를 뽑아 출력(popleft = 제거)
v = queue.popleft()
print(v, end=' ')

queue.popleft()는 큐의 선입 노드를 삭제하는 역할을 한다. 이때, 선입 노드는 1로 이를 큐에서 추출한다고 생각하면 이해가 쉬워진다.
따라서, v = 1
이후, 어떤 노드에서 while문이 실행되는지 알기 위해 노드를 출력한다.

for i in graph[1]:

graph[1] = [2, 3, 8]
1번 노드의 인접 노드인 [2, 3, 8] 각각의 요소에 대해 if문 작동
i = 2, 3, 8

if not visited[2]:
	queue.append(2)
    visited[2] = True

i = 2 일 때, 방문 정보가 없다면(False)라면, 큐 리스트에 2를 추가한다.
이후 visited를 True로 수정하여 2번 노드의 방문 정보를 수정한다.

v가 1일 때 인접 노드인 [2, 3, 8]에 대하여 수행하며 같은 방식으로 2, 3, 8에 인접한 노드를 큐에서 삭제한다.

1부터 연결된 모든 노드에 대해 방문하면 큐에서 삭제하는 작업을 반복한다. 큐가 빌 때까지 반복하면 연결된 모든 노드를 방문할 수 있다.