Algorithm, Python 탐색 알고리즘 세 가지 (완전 탐색/DFS/BFS)

알고리즘 개념 & 활용/적용 문제 예시 & 예제 코드(Python)

(작성하느라 힘들었다.

대학생 때 수업 듣던 내용 chat gpt한테 검증 받아서 셀프로 작성했다.

불펌하면 평생 탈모로 인한 변발 스타일로 살아가게 됨.

나눔고딕이 더 예쁜 것 같기도 하고 본고딕이 더 예쁜 것 같기도 하고...)

---

1. 완전 탐색 (Brute Force)

- 문제의 가능한 모든 경우를 체계적으로 나열하고 검사하여 해답을 찾는 방법

- 핵심 : 모든 가능성을 체계적으로 파악 -> 하나씩 검토

- 구현이 간단하다.

- 경우의 수가 많을 때는 비효율적 => 적을때 사용

- 적용 예 : 암호 해독, 순열 생성, 조합 탐색

- 예제 ↓

<숫자 배열의 모든 부분집합을 찾는 완전 탐색 예제>

def print_subsets(arr):
    n = len(arr)
    for i in range(2**n):
        subset = []
        for j in range(n):
            if i & (1 << j):
                subset.append(arr[j])
        print(subset)

# 예제 배열
arr = [1, 2, 3]
print_subsets(arr)

1. 함수 정의: print_subsets(arr) 함수는 주어진 배열 arr의 모든 부분집합을 출력
2. 부분집합 계산:
   • n = len(arr) : 입력 배열의 길이를 측정.
   • for i in range(2**n): 여기서 2**n은 배열의 모든 부분집합의 수를 나타냄.
   • 예를 들어, 배열에 3개의 요소가 있다면, 가능한 부분집합의 수는 2^3 = 8개.
   • i는 0부터 7까지의 값
3. 비트마스킹:
   • for j in range(n): 이 내부 루프는 배열의 각 요소에 대해 반복.
   • if i & (1 << j): 여기서 비트 연산자를 사용하여 부분집합을 확인.
     • 1 << j는 1을 왼쪽으로 j 비트만큼 이동시킴 -> j번째 비트가 1인 이진수를 생성.
     • i & (1 << j)는 i의 이진 표현에서 j번째 비트가 1인지 확인.
     • 만약 그렇다면, 해당 요소는 현재 부분집합에 포함된다.
     • 만약 j번째 요소가 현재 부분집합에 포함되면 subset.append(arr[j])를 통해 subset 리스트에 추가.

---

2. 깊이 우선 탑색 (Depth-First Search, DFS)

- 그래프 탐색 알고리즘 (그래프 구조에서 모든 정점을 방문하기 위한 알고리즘 중 하나)

- 과정

• 현재 정점에서 갈 수 있는 한 경로로 계속 감
• 더 이상 갈 곳이 없음
• 마지막으로 만난 분기점으로 돌아옴
• 다른 경로 탐색
• 모든 정점을 방문할 때까지 이 과정 반복

- 구현은 재귀 함수 또는 스택을 이용.

- 경로의 특성을 깊이 파고들어 검토할 때 유리

- 활용 예 : 미로 찾기, 퍼즐 게임, 연결 요소 찾기

- 예제  코드1↓(dict, set)

<그래프의 모든 노드를 탐색>

재귀적 방법을 사용하여 구현

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

visited = set()

def dfs(visited, graph, node):
    if node not in visited:
        print(node)
        visited.add(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)

# 'A'에서 시작
dfs(visited, graph, 'A')

1. 그래프 정의:
   • graph는 노드들의 연결 관계를 딕셔너리 형태로 나타낸다.
   • 각 키는 노드를 나타낸다
   • 해당 키의 값은 해당 노드에 인접한 노드들의 리스트이다.
2. 방문 기록 집합:
   • visited는 방문한 노드들을 기록하기 위한 집합.
   • 집합을 사용하는 이유는 중복을 허용하지 않고, 특정 요소가 집합 내에 있는지 빠르게 확인하기 위해.
3. DFS 함수:
   • dfs(visited, graph, node) 함수는 현재 노드와 연결된 모든 노드를 깊이 우선으로 탐색.
   • if node not in visited: 현재 노드가 방문한 적이 없다면, 현재 노드를 방문 처리.
   • print(node): 현재 노드를 출력.
   • visited.add(node): 현재 노드를 방문한 노드들의 집합에 추가.
   • for neighbour in graph[node]: 현재 노드에 인접한 모든 노드에 대해 반복.
   • dfs(visited, graph, neighbour): 인접한 노드에 대해 재귀적으로 같은 함수를 호출.
4. DFS 호출:
   • dfs(visited, graph, 'A')는 노드 'A'에서 시작하여 깊이 우선 탐색을 수행.

- 예제 코드2 ↓(stack)

재귀 함수를 통해 구현 (현재 노드를 방문 처리한 후, 인접한 모든 노드를 재귀적으로 탐색)

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 함수 호출
dfs(graph, 1, visited)

1. DFS 함수:
   • dfs(graph, v, visited)는 그래프에서 깊이 우선 탐색을 수행하는 함수.
   • graph는 노드들의 연결 관계를, v는 현재 방문하고 있는 노드, visited는 각 노드의 방문 여부를 나타낸다.
2. 방문 처리:
   • visited[v] = True는 노드 v를 방문했다고 표시.
   • print(v, end=' ')는 방문한 노드를 출력.
3. 인접 노드 방문:
   • for i in graph[v]: 현재 노드 v와 연결된 모든 노드에 대해 반복.
   • if not visited[i]: 만약 인접한 노드 i를 방문하지 않았다면, dfs 함수를 재귀적으로 호출하여 i 노드로 이동.
4. 그래프 정의:
   • graph는 인접 리스트로 표현된 그래프다.
   • 각 리스트의 인덱스는 노드 번호를, 해당 리스트의 요소들은 해당 노드와 연결된 다른 노드들을 나타낸다.
5. 방문 배열 초기화:
   
   • visited = [False] * 9는 총 9개의 노드에 대한 방문 여부를 저장하는 리스트를 초기화.
   • 초기에는 모든 노드를 방문하지 않았다고 가정.
6. DFS 호출:
   • dfs(graph, 1, visited)를 통해 노드 1부터 DFS 탐색을 시작.

---

3. 너비 우선 탐색 (Breadth-First Search, BFS)

- 그래프 탐색 알고리즘 (그래프 구조에서 모든 정점을 방문하기 위한 알고리즘 중 하나)

- 과정

• 시작 정점으로부터 가까운 정점을 먼저 방문
• 해당 정점들의 인접한 정점들을 다시 큐에 넣어 순서대로 탐색을 계속 진행.
• 즉 가까운 정점부터 차례대로 탐색
• 먼 정점을 나중에 방문

- 구현은 일반적으로 큐(Queue)를 사용 

- 활용 예 : 최단 경로 문제, 그래프의 연결 요소 탐색, 레벨별 탐색

- 예제 ↓(dict, queue)

<그래프의 모든 노드를 탐색>

from collections import deque

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

def bfs(graph, start_node):
    visited = set()
    queue = deque([start_node])

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            print(node)
            queue.extend(graph[node])

# 'A'에서 시작
bfs(graph, 'A')

1. 그래프 정의:
   • graph는 각 노드와 인접한 노드를 리스트로 나타낸 딕셔너리.
2. BFS 함수:
   • bfs(graph, start_node) 함수는 주어진 시작 노드에서 BFS를 수행.
3. 방문 기록 집합과 큐 초기화:
   • visited는 방문한 노드들을 기록하는 집합.
   • queue는 탐색할 노드들을 순서대로 저장하는 데 사용되는 덱(양방향 큐).
   • 선언과 동시에 시작 노드를 큐에 추가.
4. 탐색 루프:
   • while queue: 큐에 아직 탐색할 노드가 남아있는 동안 계속 진행.
   • node = queue.popleft(): 큐에서 하나의 노드를 제거.
   • FIFO(First In First Out) 원칙에 따라 가장 먼저 추가된 노드를 가져온다.
   • if node not in visited: 해당 노드를 방문하지 않았다면, 방문 처리하고 출력.
   • visited.add(node): 현재 노드를 방문한 노드의 집합에 추가.
   • queue.extend(graph[node]): 현재 노드에 인접한 노드들을 큐에 추가. 이때 이미 방문한 노드는 제외된다.
5. BFS 호출:
   • bfs(graph, 'A')는 노드 'A'에서 시작하여 너비 우선 탐색을 수행한다.