DFS/BFS

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의마한다. 이때 그래프,트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다.

! 자료구조(스택,큐) + 재귀 함수를 알아야 한다.

(실제로 사용할 때 주의할 점 : 스택과 큐를 사용할 때는 삽입과 삭제 외에도 오버플로와 언더플로를 고민해야 한다. 오버 플로는 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생한다. / 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 데잍가 전혀 없느 상태이므로 언더 플로가 발생한다.)

---

DFS

Depth-First Search라는 말로 깊이 우선 탐색이라고 부른다.

그래프를 먼저 알아야 문제를 풀 수 있다. 그래프는 노드와 간선으로 표현되며 이때 노드를 정점이라고도 말한다.

이러한 그래프를 표현하는 프로그래밍 방식은 2가지 방식이 있다.

 

1. 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식

INF = 99999999999
	
 graph = [[0,7,5],[7,0,INF],[5,INF,0]]
 
 print(graph)

2. 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하느 방식

graph = [[] for in range(3)] # 행이 3개인 2차원 리스트 인접 리스트 표현

# 노드 0에 연결된 노드 정보 저장(노드.거리)
graph[0].append((1,7)) 
ggraph[0].append((2,5))

graph[1].append((0,7))

graph[2].append((0,5))

print(graph)

이 2가지의 방식에는 메모리, 속도에 따른 차이가 있다.

• 메모리
• 인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비된다. 반면에 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용할 수 있다.
• (예시로 인접 행렬에서 노드가 5개 그래프가 있으면 우선 5x5의 인접행렬(2차원 배열)을 생성하는데 이때 이 배열은 총 25개의 공간을 차지하게 된다. 하지만 연결된 간선이 고작 1개라면 25개의 공간 중 23개는 불필요하게 낭비가 될 수 있다는 점을 의미한다.)
• 속도
• (예실 인접행렬 : matrix[u][v] 로 찾으면 바로 찾아짐. 하지만 adj_list[u] 리스트를 순회하며 v가 있는지 확인 해야 함.)
• 인접 리스트 방식은 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다. 인접 리스트 방식에서는 연결된 데이터를 하나씩 확인해야 하기 때문이다.

DFS는 스택 자료구조를 이용함.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. (탐색 → 이웃 노드 중 하나 선택하고 스택에 넣음 → 스택에 넣은 값 방문 처리 함.)
3. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
4. 2번의 과정을 더 이상 수행할 수 없을 때 까지 반복한다.

<재귀로 푸는 경우>

def dfs(graph, v, visited):
    visited[v] = True
    print(v,end=" ")
    # 그 다음에는 반복적으로 움직일 그래프들의 값을 바탕으로 탐색 해야함.
    for i in graph[v]:
        if not visited[i]:
            dfs(graph,i,visited)

graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visited = [False] * 9 

dfs(graph,1,visited)

<스택으로 푸는 경우>

def dfs_stack(graph, start, visited):
    stack = [start]
    visited[start] = True

    while stack:
        v = stack.pop()  # 스택의 맨 위에서 노드를 꺼냄
        print(v, end=' ')

        for i in reversed(graph[v]): # 거꾸로 순회해야 재귀와 동일한 출력
            if not visited[i]:
                stack.append(i)
                visited[i] = True
                
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

visited = [False] * 9 

dfs(graph,1,visited)

---

BFS

너비 우선 탐색이라는 방식은 큐 자료구조를 생각하면 된다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 반복적으로 진행한다.

import sys  
from collections import deque 

def bfs(graph, start, visited): 
    queue = deque([start]) 
    visited[start] = True 

    while queue: 
        v = queue.popleft() 
        print(v, end=" ") 
        for i in graph[v]: 
            if not visited[i]: 
                queue.append(i) 
                visited[i] = True 


graph = [ 
    [], 
    [2, 3, 8], 
    [1, 7], 
    [1, 4, 5], 
    [3, 5], 
    [3, 4], 
    [7], 
    [2, 6, 8], 
    [1, 7] 
] 

visited = [False] * 9  

bfs(graph, 1, visited)