다음과 같은 퍼즐 문제를 한 번 즈음 풀어보셨을 겁니다.
 하나의 빈 칸이 존재하고 주위의 숫자칸을 빈 칸으로 옮겨서 최종 숫자 순서대로 정렬하는 퍼즐입니다.

 다음은 미로 문제입니다.
 입구에서 출발하여 출구로 나가는 길을 찾아야 합니다. 막다른 길을 만나면 되돌아가서 다른 길을 찾아야 합니다.

 마지막으로 최적경로 찾기 문제입니다.
 매일 출퇴근하는 경로입니다. 버스를 환승하고 1호선 혹은 7호선을 이용합니다. Door to door는 1시간 40분 소요되는데... 직주근접은 정말 소중합니다...
이처럼 우리는 종종 목적지까지 가장 빠른 길을 찾아야 할 때가 있습니다.

 과연 이 문제들을 어떻게 논리적으로 해결할 수 있을까요?

 검색 알고리즘은 위와 같은 문제들에 대한 답을 구할 수 있습니다.

 검색 알고리즘은 연속 변수나 이산 변수를 사용하여 일부 데이터 구조 안에 저장된 정보를 검색하거나 검색 공간에서 계산을 하기 위해 사용합니다.

 에이전트 ^agent는 주변 환경 ^environment을 인식하고 상호작용하는 주체입니다. 환경 내에서 에이전트가 배치된 모양을 상태^state라고 일컫습니다. 에이전트에게 어떤 환경 안에서 문제가 주어졌을 때 현명한 결정을 내리려면 어떤 행동 ^actions이 가장 좋은지 검색하고 실행에 옮겨야 합니다. 현실에서 곧바로 실행할 수 없기 때문에 모델을 사용하여 simulation을 합니다.
 이처럼 검색 과정을 통해 다양한 솔루션 ^solution을 얻을 수 있으며 가장 비용이 적게 드는 솔루션을 optimal solution이라고 합니다.

 검색 문제는 다음과 같이 구성됩니다.

• ⊙ 초기 상태 ^{initial state}: 에이전트가 환경 안에서 행동을 시작하기 전 초기 위치입니다.
• ⊙ 행동 ^actions: 현재 상태에서 선택 가능한 행동들을 의미합니다. ACTIONS(s)는 상태 s에서 실행가능한 모든 행동들을 반환합니다.
• ⊙ 전이모델 ^{transition model}: 특정 상태에서 가능한 행동을 수행한 결과 나타나는 상태들을 설명하는 모델입니다. RESULT(s, a)는 상태 s에서 행동 a를 수행한 결과 상태를 반환합니다.
• ⊙ 평가 ^{goal test}: 행동의 결과로 얻어진 상태가 처음 목표로 했던 상태인지 평가하는 것입니다.
• ⊙ 비용 함수 ^{path cost function}: 주어진 경로를 거쳐감에 따라 소요되는 비용을 산출하는 함수입니다.

 검색 문제는 아래와 같은 과정에 따라 접근합니다.
 1. Frontier는 초기 상태(A)를 포함한 상태, Explored set은 비어있는 상태에서 시작합니다.
 2. 아래 과정들을 반복합니다.
   1) Frontier에 검색할 다음 노드 ^node가 존재하는지 확인합니다. 만약 비어 있다면 솔루션은 없으며 검색 과정을 종료합니다. 참고로 노드란 상태 ^state, 부모 노드 ^{parent node}, 행동 ^action, 비용 ^{path cost}에 대한 정보를 담고 있는 데이터 구조라고 볼 수 있습니다.
    2) 노드 가져오기: Frontier에서 마지막 노드를 추출합니다. (stack 구조)
    3) 솔루션 확인과 리턴: 만약 2)의 노드가 목표하는 노드라면 검색과정을 종료하고 솔루션을 리턴합니다.
    4) 노드 추가: Explored set에 노드를 추가합니다.
    5) Frontier 확장: Frontier에 하위 노드(child node)를 추가합니다. 이 때 하위 노드가 frontier와 explored set에 존재하는지 확인합니다. 만약 존재한다면 하위 노드는 추가할 수 없습니다.

 위 과정에서 어떤 특징을 찾아볼 수 있을까요?
 검색 과정에서 마지막 노드(F)를 만날 때까지 계속 하위 노드를 찾아갑니다. 마지막 노드(F)에 다다르면 목표 노드(E)와 일치하는지 비교합니다. 만약 목표 노드와 일치하지 않는다면 다시 마지막 분기 지점(B)으로 돌아가서 같은 방식으로 검색을 이어갑니다. 다시 마지막 노드(E)에 다다르면 목표 노드(E)와 일치하는지 비교합니다. 일치한다면 검색 과정을 종료합니다.
 이처럼 가장 깊은 단계 노드까지 확장하며 검색하는 방식이 DFS ^{Depth First Search}입니다. DFS는 stack 구조를 사용하여 노드를 검색합니다.

 노드의 수를 V ^Vertex, 연결선의 수를 E ^Edge라고 할 때, DFS의 공간 복잡도는 인접행렬인 경우: O(V^2), 인접리스트인 경우: O(V + E) 입니다. 시간 복잡도는 인접행렬인 경우: O(V^2), 인접리스트인 경우: O(V + E) 입니다.

 DFS의 장, 단점은 아래와 같습니다.

 DFS를 미로찾기 문제에 적용해 보겠습니다.

 'Node' 클래스는 노드 객체를 생성합니다. 노드는 에이전트의 상태, 부모 노드, 그리고 행동에 대한 정보를 가지고 있습니다.

 DFS는 stack 구조를 사용하여 노드를 검색합니다.
 'StackFrontier()' 클래스는 우선 비어있는 리스트 형태의 frontier 객체를 생성합니다.
 'add' 함수는 frontier에 노드를 추가합니다. 다음 단계 노드(자식 노드)를 frontier에 추가합니다.
 'contains_state' 함수는 노드가 이미 frontier에 들어있는지 검사합니다.
 'empty' 함수는 frontier에 담긴 노드 수가 0인지 확인합니다. Frontier에 더이상 가져올 노드가 없는지 확인하는 함수입니다.
 'remove' 함수가 본 클래스의 핵심입니다. DFS는 stack 구조를 사용합니다. 따라서 frontier의 가장 마지막 위치에 존재하는 노드를 가져옵니다.

 파일로부터 미로찾기 문제를 읽고 시작(S)에서 끝(E)까지 경로를 찾는 과정입니다.
 'Maze()' 클래스는 미로찾기 문제가 담긴 파일을 읽습니다. 시작 위치(S), 종료 위치(E), 벽, 그리고 길을 파악하여 r^row * c^column 크기의 행렬로 정리합니다.
 'print_out' 함수는 미로와 솔루션을 출력합니다.
 'neighbors' 함수는 현재 노드에서 이동 가능한 노드로의 방향과 그 좌표를 확인하고 모두 리턴합니다.
 'solve' 함수는 솔루션을 발견하거나 더이상 frontier에 검색할 노드가 남아있지 않을 때까지 검색 과정을 반복 수행합니다.
 'output_image' 함수는 미로와 발견한 솔루션을 이미지 파일로 출력해주는 역할을 합니다.

 전체 코드와 예제 파일은 이 곳에서 확인할 수 있습니다.

 실제 미로 문제 파일을 입력받아 코드가 솔루션을 찾아내는 과정을 실행해 보겠습니다.

 하지만 DFS의 단점으로 알아봤던 것처럼 항상 최적의 솔루션을 찾는 것은 아닙니다. 위 예시에서도 maze3.txt의 경우 가까운 길을 두고 먼 길을 돌아서 찾아간 것을 볼 수 있습니다. 그렇다면 이런 경우 최적의 솔루션을 어떻게 찾을 수 있을까요? 바로 BFS ^{Breathe First Search}를 사용하는 것입니다.