---

Reference

• 2309번 일곱 난쟁이, Baekjoon online judge
• 24444번 알고리즘 수업 - 너비 우선 탐색 1, Baekjoon online judge
• 24479번 알고리즘 수업 - 깊이 우선 탐색 1, Baekjoon online judge

---

1. 브루트 포스

브루트 포스 탐색(Brute-force search): 가능한 모든 경우를 확인.
-Reference. Brute-force search

• 선형 구조: 순차 탐색
• 비선형 구조: 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

1.1. 순차 탐색

순차 검색 알고리즘(sequential search algorithm): 리스트에서 특정한 값을 찾는 알고리즘. 리스트에서 찾고자 하는 값을 맨 앞에서부터 끝까지 찾아 나가는 방법.
-Reference. Linear search

---

1.1.1. 순차 탐색 알고리즘

순차 탐색 알고리즘을 파이썬으로 구현하면 다음과 같다.

def linear_search(x: int, where: list) -> int:
	for i in range(len(where)):
    	if x == where[i]:
        	return i
    return -1

print(linear_search(3, [1, 2, 3, 4, 5]))

>>> 2

---

1.1.2. [백준 2309번] 일곱 난쟁이

위의 1.1.1. 순차 탐색 알고리즘을 활용하여 다음과 같이 파이썬으로 문제를 풀이할 수 있다.

import sys
import heapq

dwarfs = []
for _ in range(9):
    dwarfs.append(int(sys.stdin.readline()))

flag: bool = False
for i in range(8):
    for j in range(i+1, 9):
        if sum(dwarfs) - dwarfs[i] - dwarfs[j] == 100:
            del dwarfs[j]
            del dwarfs[i]
            flag = True
            break
    if flag:
        break

heapq.heapify(dwarfs)
for _ in range(7):
    print(heapq.heappop(dwarfs))

---

1.2. 너비 우선 탐색(BFS)

너비 우선 탐색(Breath-first search, BFS): 리(tree) 혹은 그래프(graph) 자료구조를 순회하거나 탐색하는 알고리즘. 하나의 node에서 시작해서 인접한 모든 node들을 우선 방문하여 탐색하는 방법.
-Reference. Breadth-first search

• 너비를 우선으로 하여 탐색
• 큐(queue, FIFO) 자료구조를 이용하여 구현

1.2.1. 너비 우선 탐색 알고리즘

• 탐색을 시작할 노드를 큐에 enqueue 후 방문 체크
• 큐에서 노드를 dequeue 하여 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 enqueue 후 방문 체크
• 위의 과정을 반복

너비 우선 탐색 알고리즘을 파이썬으로 구현하면 다음과 같다.

def BFS(graph: dict(), start_node: str) -> list:
    visited = []
    queue = []
    
    queue.append(start_node)
    
    while queue:
        current_node = queue.pop(0)
        if current_node not in visited:
            visited.append(current_node)
            queue.extend(graph[current_node])
            
    return visited

graph = {
    'A': ['B'],
    'B': ['A', 'C', 'H'],
    'C': ['B', 'D'],
    'D': ['C', 'E', 'G'],
    'E': ['D', 'F'],
    'F': ['E'],
    'G': ['D'],
    'H': ['B', 'I', 'J', 'M'],
    'I': ['H'],
    'J': ['H'],
    'M': ['H']
}

print(BFS(graph, "A"))

>>> ['A', 'B', 'C', 'H', 'D', 'I', 'J', 'M', 'E', 'G', 'F']

---

1.2.2. [백준 24444번] 알고리즘 수업 - 너비 우선 탐색 1

위의 1.2.1. 너비 우선 탐색 알고리즘을 활용하여 다음과 같이 파이썬으로 문제를 풀이할 수 있다.

import sys

def BFS(graph: dict(), start_node: int, visited: list()) -> list():
    queue = []
    count = 1
    
    queue.append(start_node)
    
    while queue:
        current_node = queue.pop(0)
        if visited[current_node] == 0:
            visited[current_node] = count
            count += 1
            queue.extend(graph[current_node])
    return visited

graph = dict()
N, M, R = list(map(int, sys.stdin.readline().split()))
for i in range(N):
    graph[i + 1] = []
for _ in range(M):
    u, v = list(map(int, sys.stdin.readline().split()))
    graph[u].append(v)
    graph[v].append(u)
for i in range(N):
    graph[i + 1].sort()
visited = [0]*(N+1)
visited = BFS(graph, R, visited)
for i in range(N):
    print(visited[i+1])

하지만, BFS 알고리즘의 큐를 list로 구현할 경우 pop() 함수 호출시 원소를 이동해야하므로 시간 복잡도가 증가한다.
따라서, 다음과 같이 파이썬 collections.deque 라이브러리를 사용하여 구현해야 한다.

import sys
from collections import deque

def BFS(graph: dict(), start_node: int, visited: list()) -> list():
    queue = deque()
    count = 1
    
    queue.append(start_node)
    
    while queue:
        current_node = queue.popleft()
        if visited[current_node] == 0:
            visited[current_node] = count
            count += 1
            queue.extend(graph[current_node])
    return visited

graph = dict()
N, M, R = list(map(int, sys.stdin.readline().split()))
for i in range(N):
    graph[i + 1] = []
for _ in range(M):
    u, v = list(map(int, sys.stdin.readline().split()))
    graph[u].append(v)
    graph[v].append(u)
for i in range(N):
    graph[i + 1].sort()
visited = [0]*(N+1)
visited = BFS(graph, R, visited)
for i in range(N):
    print(visited[i+1])

---

1.3. 깊이 우선 탐색(DFS)

깊이 우선 탐색(Depth-first search, DFS): 트리(tree) 혹은 그래프(graph) 자료구조를 순회하거나 탐색하는 알고리즘. 하나의 node에서 시작해서 백트래킹(backtracking) 전까지 가능한 멀리 탐색하는 방법.
-Reference. Depth-first search

• 깊이를 우선으로 하여 탐색
• 스택(stack, LIFO) 자료구조를 이용하여 구현

1.3.1. 깊이 우선 탐색 알고리즘

• 탐색을 시작할 노드를 스택에 push 후 방문 체크
• 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 push 후 방문 체크
• 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드 pop
• 위의 과정을 반복

깊이 우선 탐색 알고리즘을 파이썬으로 구현하면 다음과 같다.

def DFS(graph: dict(), start_node: str) -> list():
    visited = []
    stack = []
    
    stack.append(start_node)
    
    while stack:
        current_node = stack.pop()
        if current_node not in visited:
            visited.append(current_node)
            stack.extend(graph[current_node])
            
    return visited

graph = {
    'A': ['B'],
    'B': ['A', 'C', 'H'],
    'C': ['B', 'D'],
    'D': ['C', 'E', 'G'],
    'E': ['D', 'F'],
    'F': ['E'],
    'G': ['D'],
    'H': ['B', 'I', 'J', 'M'],
    'I': ['H'],
    'J': ['H'],
    'M': ['H']
}

print(DFS(graph, "A"))

>>> ['A', 'B', 'H', 'M', 'J', 'I', 'C', 'D', 'G', 'E', 'F']

---

1.3.2. [백준 24479번] 알고리즘 수업 - 깊이 우선 탐색 1

위의 1.3.1. 깊이 우선 탐색 알고리즘을 활용하여 다음과 같이 파이썬으로 문제를 풀이할 수 있다.

import sys
from collections import deque

def DFS(graph: dict(), start_node: int, visited: list()) -> list():
    stack = deque()
    count = 1
    
    stack.append(start_node)
    
    while stack:
        current_node = stack.pop()
        if visited[current_node] == 0:
            visited[current_node] = count
            count += 1
            stack.extend(graph[current_node])
    return visited

N, M, R = list(map(int, sys.stdin.readline().split()))
graph = dict()
for i in range(N):
    graph[i+1] = []
for _ in range(M):
    u, v = list(map(int, sys.stdin.readline().split()))
    graph[u].append(v)
    graph[v].append(u)
for i in range(N):
    graph[i+1].sort(reverse=True)
visited = [0]*(N+1)
visited = DFS(graph, R, visited)
for i in range(N):
    print(visited[i+1])