탐색과 문제 해결

길을 찾는 방법, 탐색(Search)

인공지능은 정답으로 가는 길을 어떻게 찾아낼까?

인공지능이 문제를 해결하는 핵심 과정, 「탐색」의 개념을 알아봅시다.

탐색 (Search)

인공지능이 주어진 문제를 해결하기 위해, 지금 상태에서 할 수 있는 행동을 하나씩 적용해 가며 초기 상태에서 목표 상태로 이어지는 경로를 찾아 가는 과정입니다.

한 상태에서 갈 수 있는 다음 상태들을 만들어 트리에 붙이는 일을 그 노드를 확장(expand)한다고 합니다. 경로를 찾기만 하면 되므로, 가능한 길을 하나도 빠짐없이 다 확장해 보아야 하는 것은 아닙니다. 모두 확장해 보는 방법도 있고, 유망해 보이는 쪽부터 골라 보는 방법도 있습니다.

상태 공간 (State Space)

초기 상태에서 출발해 규칙에 맞는 행동을 계속 적용했을 때 도달할 수 있는 모든 상태의 집합입니다. 주로 점(노드)과 선(간선)으로 이루어진 그래프나 트리 형태로 그립니다.

여기서 상태란 문제가 진행되는 도중의 한 장면을 말합니다. 다섯 요소는 「탐색 문제의 다섯 요소」 절에서 하나씩 살펴봅니다.

내비게이션 앱마다 경로가 다른 이유는?

인공지능이 주어진 문제를 스스로 해결하기 위해 정답으로 가는 과정을 체계적으로 찾아나가는 것을 탐색(Search)이라고 합니다. 목록에서 값 하나를 찾는 일도 탐색이라 부르지만, 여기서 찾는 것은 값이 아니라 목표 상태나 그에 이르는 경로입니다.

출발지와 도착지는 같아도, 어떤 내비게이션은 「가장 거리가 짧은 길」을 찾고, 다른 내비게이션은 「차가 안 막혀서 시간이 적게 걸리는 길」을 찾습니다. 즉, 무엇을 「좋은 길」로 볼지 정한 탐색의 기준이 앱마다 다르기 때문입니다.

사실 우리도 하루에 몇 번씩 탐색을 한다

탐색은 인공지능만의 특별한 기술이 아닙니다. 우리는 여러 갈래의 가능성 앞에서 더 나은 쪽을 골라 가며 문제를 풉니다. 인공지능이 하는 일도 결국 같은 일을 컴퓨터가 따라 할 수 있게 정리한 것입니다.

약속 장소로 갈 때

지하철·버스·자전거 중 오늘 가장 빠른 조합을 머릿속으로 비교해 봅니다.

요리를 할 때

밥을 먼저 안칠지 재료를 먼저 썰지, 순서에 따라 걸리는 시간이 달라집니다.

보드게임을 둘 때

「내가 여기 두면 상대는 저기 두겠지」를 몇 수 앞까지 그려 봅니다.

탐색은 인공지능에서 가장 오래된 연구 분야 가운데 하나입니다. 체스나 바둑을 두는 프로그램, 퍼즐을 푸는 프로그램은 모두 여기서 출발했습니다.

탐색은 「학습」이 아닌데, 왜 인공지능일까?

인공지능이 판단하는 방법은 탐색 · 지식 표현과 추론 · 기계학습 세 갈래로 나뉩니다. 탐색은 그중 하나입니다. 탐색하는 프로그램은 데이터를 모아 스스로 규칙을 배우지 않습니다. 사람이 상태와 규칙을 정해 주면, 그 규칙 안에서 길을 고르는 일만 합니다.

그런데도 인공지능이라 부르는 까닭은, 인공지능인지 아닌지를 구분하는 기준이 학습을 하느냐가 아니라 상황을 보고 무엇을 할지 스스로 고르느냐이기 때문입니다. 갈림길마다 어느 쪽으로 갈지 정하는 일 자체가 이미 그 판단입니다.

스스로 확인

탐색하는 프로그램은 데이터로 학습하지 않는데도 인공지능이라고 부릅니다. 그 까닭을 한 문장으로 말해 볼까요?

탐색 문제의 다섯 요소

문제를 어떤 말로 다시 써야 탐색으로 풀 수 있을까?

모든 탐색 문제가 공유하는 다섯 가지 뼈대를 익혀 봅시다.

탐색 문제는 이 다섯 가지가 정해져야 풀 수 있다

「탐색으로 푼다」는 말은 곧 문제를 아래 다섯 가지 언어로 다시 쓴다는 뜻입니다. 이 다섯 가지가 정해지지 않으면 인공지능은 무엇을 어디까지 찾아야 하는지 알 수 없습니다. 뒤에서 다룰 미로·8-퍼즐·n-Queen·강 건너기·하노이의 탑은 모두 이 표의 빈칸을 채우는 연습입니다.

요소	뜻	내비게이션이라면
① 상태 (State)	문제 상황을 한 장면으로 찍은 것. 무엇을 기록해야 그 장면이 완전히 설명되는가를 정하는 일입니다.	지금 내 차가 서 있는 지점
② 초기 상태	문제가 처음 주어졌을 때의 상태. 상태 공간 트리의 루트 노드가 됩니다.	출발지
③ 목표 상태	도달하면 문제가 풀린 상태. 「이 상태가 목표인가?」를 판별할 수 있어야 합니다.	목적지
④ 연산자 (Operator)	한 상태를 다른 상태로 바꾸는 규칙(행동). 트리에서 간선 하나가 연산자 한 번에 해당합니다.	다음 교차로까지 한 구간 주행
⑤ 경로 비용	초기 상태에서 그 상태까지 오는 데 든 비용의 합. 여러 해답 중 더 좋은 해답을 고르는 기준이 됩니다.	지금까지 달린 거리 또는 걸린 시간

상태 공간(State Space)은 초기 상태에서 출발해 연산자를 계속 적용했을 때 도달할 수 있는 모든 상태의 집합입니다. 즉 상태 공간은 문제를 낼 때 주어지는 것이 아니라, ①·②·④를 정하는 순간 자동으로 결정됩니다.

왜 하필 퍼즐과 게임으로 탐색을 배울까?

8-퍼즐이나 n-Queen을 배우면서 「이게 탐색이랑 무슨 상관이지?」라는 의문이 드는 것은 자연스럽습니다. 이 퍼즐들은 퍼즐을 잘 풀기 위해 배우는 것이 아니라, 위의 다섯 요소가 눈에 보이는 가장 작은 문제이기 때문에 배웁니다.

현실 문제 (예: 자율주행 경로 계획)

상태가 무엇인지조차 눈에 보이지 않고, 상태 공간이 사실상 무한합니다. 초보자가 여기서 시작하면 아무것도 확인할 수 없습니다.

퍼즐 문제 (예: 8-퍼즐)

상태를 그림 한 장으로 그릴 수 있고, 연산자가 네 가지뿐이며, 목표 상태를 한눈에 판별할 수 있습니다. 탐색 알고리즘이 실제로 무엇을 하는지 손으로 따라갈 수 있습니다.

퍼즐은 탐색의 축소 모형입니다. 퍼즐에서 익힌 「상태 → 연산자 → 상태 공간 트리」 구조를 그대로 크게 키운 것이 내비게이션 경로 탐색이고 로봇 동작 계획입니다. 그래서 이 단원의 진짜 학습 목표는 퍼즐 푸는 방법이 아니라 주어진 문제를 상태 공간 트리로 바꿔 쓰는 능력입니다.

스스로 확인

「자판기에서 음료 하나 사기」를 탐색 문제로 쓴다면, 상태·초기 상태·목표 상태·연산자·경로 비용에 각각 무엇을 적을까요?

트리(Tree)부터 차근차근

상태 공간 트리를 그리려면 어떤 말부터 알아야 할까?

상태 공간 트리를 그리려면 먼저 트리라는 자료구조의 말부터 익혀야 합니다.

트리의 구성 요소

트리는 점(노드)과 선(간선)으로 이루어진 그림인데, 나무를 거꾸로 세운 모양이라 트리라고 부릅니다. 맨 위에 뿌리가 하나 있고, 아래로 갈수록 가지가 나뉩니다. 아래 그림의 용어를 먼저 확실히 익혀 둡시다.

용어	뜻	위 그림에서
노드 (Node)	상태 하나를 담는 점. 「정점(Vertex)」이라고도 합니다.	A·B·C·D·E·F 여섯 개
간선 (Edge)	두 노드를 잇는 선. 연산자를 한 번 적용했다는 뜻입니다.	A–B, A–C, B–D, B–E, C–F 다섯 개
루트 노드 (Root)	부모가 없는 맨 위 노드. 탐색에서는 초기 상태가 놓입니다.	A
부모 노드 (Parent)	어떤 노드 바로 위에 간선으로 연결된 노드. 루트가 아닌 노드의 부모는 늘 하나뿐입니다.	D의 부모는 B, B의 부모는 A
자식 노드 (Child)	어떤 노드 바로 아래에 연결된 노드. 연산자를 적용해 만들어 낸 새 상태입니다.	A의 자식은 B와 C
형제 노드 (Sibling)	부모가 같은 노드들. 같은 상태에서 서로 다른 선택을 한 결과입니다.	D와 E, B와 C
잎 노드 (Leaf)	자식이 없는 노드. 목표 상태이거나, 막다른 길이거나, 아직 확장하지 않은 상태입니다.	D, E, F
깊이 (Depth) · 레벨	루트에서 그 노드까지 지나온 간선의 개수. 곧 연산자를 적용한 횟수입니다.	A는 0, B·C는 1, D·E·F는 2
가지 (Branch)	한 노드와 그 아래에 딸린 전체. 더 볼 필요가 없는 가지를 탐색에서 빼는 것을 가지치기라고 합니다.	B와 그 아래 D·E

여기서 자주 막힙니다. 「트리랑 그래프랑 뭐가 달라요?」

둘은 서로 다른 종류의 그림이 아닙니다. 그래프(graph)와 트리(tree)는 모두 노드(node, 정점)와 간선(edge, 엣지)으로 이루어진 자료구조입니다. 바로 위 표에서 익힌 노드와 간선이 양쪽에 그대로 쓰입니다. 다른 것은 노드를 잇는 방식 하나뿐입니다. 아래 두 그림을 나란히 보세요.

그래프(graph)

되돌아오는 길이 있어도 된다

A에서 B로, B에서 C로 간 다음 다시 A로 돌아올 수 있습니다(빨간 삼각형). C는 A와도 B와도 이어져 있어 위쪽 이웃이 둘입니다.

트리(tree)

되돌아오는 길이 없다

어느 노드에서 출발해도 지나온 간선을 되돌아가지 않고서는 같은 노드로 되돌아오지 못합니다. B와 C를 잇는 선이 없으니 루트 A를 뺀 모든 노드의 부모는 하나뿐입니다.

두 그림의 차이는 간선 B–C 하나뿐입니다. 그 하나가 있으면 되돌아오는 길, 곧 사이클이 생깁니다. 그래프는 사이클이 있어도 되고 부모가 여럿이어도 되지만, 트리는 사이클이 없고 부모가 하나뿐인 그래프입니다. 즉 트리는 그래프의 한 종류이지, 그래프와 나란히 놓인 다른 것이 아닙니다.

탐색을 잘하려면 일어날 수 있는 모든 경우의 수, 즉 상태 공간을 구조화해야 합니다. 상태 공간을 나무가 가지를 뻗어나가는 형태로 표현한 것을 상태 공간 트리(줄여서 탐색 트리)라고 합니다.

초기 상태 (Start) 문제가 처음 주어졌을 때의 시작점. 나무의 뿌리에 해당합니다.
목표 상태 (Goal) 우리가 찾고자 하는 정답이나 목적지입니다.
경로 탐색 (Path) 초기 상태에서 목표 상태까지 여러 경우의 수(가지)를 따라 내려가는 과정입니다.

스스로 확인

그림의 트리에서 F 아래에 자식 G를 하나 더 달면, 잎 노드는 어느 것들이 되나요? F는 여전히 잎 노드일까요?

문제를 상태 공간 트리로 구조화하기

눈앞의 문제를 어떻게 상태 공간 트리로 바꿔 쓸까?

탐색 알고리즘을 외우는 것보다 훨씬 어려운 일은 주어진 문제를 트리로 바꿔 쓰는 일입니다. 다섯 가지 문제를 하나씩 같은 틀에 넣어 봅시다. 탭은 대체로 상태 공간이 작은 문제부터 놓았습니다. 다만 n-Queen은 경로가 아니라 배치를 찾는 문제라서 성격이 달라 맨 끝에 두었습니다.

다섯 탭 모두 같은 표를 채웁니다. 문제는 전혀 달라 보여도 ①상태 ②초기 상태 ③목표 상태 ④연산자 ⑤경로 비용만 정하면 똑같이 트리가 만들어진다는 것을 확인해 보세요.

농부의 강 건너기

상태가 지도 위 위치가 아니라 「조합」인 문제. 금지 상태는 가지치기로 걸러 낸다.

문제와 규칙

농부가 늑대·양·양배추를 데리고 강을 건너야 합니다.
배에는 농부와 한 가지만 탈 수 있습니다. 배는 농부만 저을 수 있습니다.
농부가 없는 쪽에 늑대와 양만 남으면 늑대가 양을 먹습니다.
농부가 없는 쪽에 양과 양배추만 남으면 양이 양배추를 먹습니다.

상태를 어떻게 적을까?

여기에는 「좌표」가 없습니다. 필요한 정보는 오직 농부·늑대·양·양배추가 각각 어느 쪽 강가에 있는가뿐입니다. 넷이 각각 왼쪽(왼) 또는 오른쪽(오)이므로 상태 하나는 기호 네 개로 적을 수 있습니다.

농부 늑대 양 양배추 (왼, 왼, 오, 왼)은 양만 건너간 상태입니다

① 상태	(농부, 늑대, 양, 양배추)가 각각 어느 쪽 강가에 있는지
② 초기 상태	(왼, 왼, 왼, 왼) — 모두 왼쪽 강가
③ 목표 상태	(오, 오, 오, 오) — 모두 오른쪽 강가
④ 연산자	농부가 배를 타고 반대편으로 건너기. 혼자 / 늑대와 / 양과 / 양배추와 — 최대 4가지. 단, 데려갈 대상은 농부와 같은 쪽에 있어야 합니다.
⑤ 경로 비용	강을 건넌 횟수. 최소 7번이면 해결됩니다.
상태 공간 크기	넷이 각각 두 곳이므로 2⁴ = 16가지. 그중 규칙을 어기지 않는 유효한 상태는 10개뿐입니다.

첫 수의 자식 4개 중 셋이 즉시 잘려 나간다

(왼, 왼, 왼, 왼)

농부 혼자

✗ 늑대가 양을 먹음

늑대와 함께

✗ 양이 양배추를 먹음

양과 함께

✓ (오, 왼, 오, 왼)

양배추와 함께

✗ 늑대가 양을 먹음

첫 수는 양을 데려가는 것뿐입니다. 나머지 셋은 만들자마자 규칙 위반이라 더 볼 필요가 없습니다. 이렇게 금지 상태로 가는 가지를 탐색에서 빼는 일이 가지치기입니다. 그림에서는 보이려고 노드를 그린 뒤 잘라 냈습니다.

횟수	연산자	건넌 뒤 상태 (농부, 늑대, 양, 양배추)
1	양과 함께 →	(오, 왼, 오, 왼)
2	← 혼자 돌아옴	(왼, 왼, 오, 왼)
3	늑대와 함께 →	(오, 오, 오, 왼)
4	← 양을 다시 데려옴	(왼, 오, 왼, 왼)
5	양배추와 함께 →	(오, 오, 왼, 오)
6	← 혼자 돌아옴	(왼, 오, 왼, 오)
7	양과 함께 →	(오, 오, 오, 오) 목표 도달

여기서 배울 것

상태 공간은 지도가 아니어도 됩니다. 「누가 어느 쪽에 있는가」라는 조합도 상태가 될 수 있습니다.
4번째 수에서 양을 다시 왼쪽으로 데려옵니다. 목표에서 멀어지는 것처럼 보이는 이동이 정답 경로에 반드시 필요합니다. 눈앞의 이득만 좇는 방법이 왜 위험한지 이 장면이 보여 줍니다.
규칙을 어긴 상태는 노드에서 즉시 제거합니다. 16개 중 6개가 이렇게 사라져 유효 상태는 10개가 됩니다.

미로 찾기

가장 직관적인 예. 상태가 곧 「내가 서 있는 칸」이다.

5×5 격자 미로입니다. 검은 칸은 벽이라 지나갈 수 없고, 회색 칸은 지나갈 수 있습니다. S에서 출발해 G까지 가야 합니다.

사람은 미로를 그림 전체로 봅니다. 하지만 인공지능에게 미로는 그림이 아니라 「현재 칸」이라는 상태 하나와, 그 칸에서 갈 수 있는 이웃 칸의 목록일 뿐입니다. 이 관점의 전환이 상태 공간 트리의 출발점입니다.

지나갈 수 있는 칸은 모두 18칸입니다. 곧 이 미로의 상태 공간 크기는 18입니다.

① 상태	지금 서 있는 칸의 좌표 (행, 열). 숫자 두 개면 상태 하나가 완전히 표현됩니다.
② 초기 상태	S가 있는 칸 (0, 0)
③ 목표 상태	G가 있는 칸 (4, 4)
④ 연산자	위·아래·왼쪽·오른쪽으로 한 칸 이동 (최대 4가지). 단, 벽이거나 격자 밖이면 그 연산자는 적용할 수 없습니다.
⑤ 경로 비용	이동한 칸 수. 한 번 이동에 비용 1이므로 경로 비용 = 트리의 깊이가 됩니다.
상태 공간 크기	벽이 아닌 칸의 수 = 18개

미로는 사실 그래프입니다. 왔던 칸으로 되돌아갈 수 있으니까요. 그런데 탐색에서는 「이미 방문한 상태는 다시 방문하지 않는다」는 규칙을 두면, 그래프를 초기 상태를 뿌리로 하는 트리로 전개해서 다룰 수 있습니다. 상태 공간 트리라는 이름은 여기서 나옵니다. 아래에서 미로가 트리로 전개되는 과정을 직접 보세요.

미로가 트리로 자라나는 과정 보기

현재 칸(주황)에서 갈 수 있는 이웃 칸을 자식 노드로 매답니다. 이미 트리에 올라온 칸은 다시 노드로 만들지 않습니다 — 이것이 그래프를 트리로 전개하는 규칙입니다.

여기서 배울 것

노드 = 칸, 간선 = 한 칸 이동. 한 칸 이동의 비용이 모두 1로 같기 때문에 깊이가 곧 이동 횟수가 되고, 그래서 더 얕은 곳에서 찾은 답이 더 짧은 경로입니다. 간선마다 비용이 다른 문제(예: 구간마다 걸리는 시간이 다른 도로)에서는 이 말이 성립하지 않습니다.
자식이 하나뿐인 구간에서는 트리가 한 줄로만 뻗습니다. 갈림길에서만 가지가 나뉩니다.
더 갈 곳이 없는 칸은 잎 노드(막다른 길)가 되고, 탐색은 되돌아갑니다.

하노이의 탑

연산자에 조건이 붙는 문제. 상태 공간이 폭발적으로 커지는 모습을 수식으로 볼 수 있다.

기둥이 셋, 크기가 다른 원판이 셋 있습니다. 원판을 모두 A에서 C로 옮기되, 한 번에 원판 하나만 옮길 수 있고 큰 원판을 작은 원판 위에 올릴 수 없습니다.

① 상태	원판마다 어느 기둥에 있는지. 작은 원판부터 적어 (A, A, A)처럼 표현합니다. 같은 기둥 안의 순서는 규칙상 항상 큰 것이 아래이므로 따로 적을 필요가 없습니다.
② 초기 상태	(A, A, A) — 세 원판 모두 A
③ 목표 상태	(C, C, C) — 세 원판 모두 C
④ 연산자	한 기둥의 맨 위 원판을 다른 기둥의 맨 위로 옮기기. 기둥 쌍이 3가지이므로 대부분의 상태에서 이동 가능한 수는 3가지이고, 세 원판이 모두 한 기둥에 모인 상태(시작·완성 상태 등)에서는 2가지입니다.
⑤ 경로 비용	원판을 옮긴 횟수. 원판이 n개일 때 최소 2ⁿ − 1번, 3개면 7번입니다.
상태 공간 크기	원판마다 기둥 세 곳 중 하나이므로 3ⁿ개. 3개면 27개, 10개면 59,049개입니다.

초기 상태의 자식은 2개뿐 — 움직일 수 있는 것은 맨 위 원판 하나

(A, A, A)

가장 작은 원판 A→B

(B, A, A)

가장 작은 원판 A→C

(C, A, A)

중간·큰 원판은 위에 다른 원판이 얹혀 있어 연산자를 적용할 수 없습니다. 미로에서 벽이 이동을 막았듯, 여기서는 규칙이 연산자를 막습니다. 원판이 3개일 때 최단 경로는 깊이 7입니다.

여기서 배울 것

연산자는 언제나 쓸 수 있는 것이 아니라 조건(전제)이 붙습니다. 조건을 어기는 이동은 간선이 되지 못합니다.
원판이 하나 늘 때마다 상태 공간은 3배, 최소 이동 횟수는 2배 남짓으로 늘어납니다. 문제 크기가 조금만 커져도 트리가 감당할 수 없이 커진다는 사실을 수식으로 확인할 수 있습니다.
이 폭발 때문에 모두 확장해 보지 않고도 좋은 길을 고르는 방법이 필요합니다.

8-퍼즐

상태가 「한 지점」이 아니라 「판 전체의 배치」일 수 있음을 보여 주는 문제.

초기 상태

123 46 758

목표 상태

123 456 78

3×3 판에 1~8 타일과 빈칸 하나가 있습니다. 타일을 빈칸으로 밀어서 목표 배치를 만드는 것이 문제입니다. 미로에서는 상태가 좌표 두 개였지만, 여기서는 아홉 칸에 무엇이 놓여 있는지 전부가 상태 하나입니다. 이 문제는 「상태 = 위치」라는 생각을 깨 줍니다.

① 상태	아홉 칸의 배치 전체. 예를 들어 위 초기 상태는 (1,2,3,4,_,6,7,5,8)처럼 숫자 아홉 개로 적을 수 있습니다.
② 초기 상태	문제로 주어진 섞인 배치
③ 목표 상태	1~8이 차례대로 놓이고 빈칸이 오른쪽 아래에 있는 배치
④ 연산자	빈칸을 위·아래·왼쪽·오른쪽으로 옮기기 (최대 4가지). 빈칸이 가운데면 4가지, 네 변의 가운데 칸이면 3가지, 네 구석이면 2가지뿐입니다.
⑤ 경로 비용	타일을 민 횟수. 역시 비용 = 깊이입니다.
상태 공간 크기	아홉 칸에 아홉 개를 늘어놓는 경우의 수 9! = 362,880. 그중 실제로 도달할 수 있는 것은 절반인 181,440개입니다.

연산자를 「타일을 옮긴다」로 잡으면 안 되는 이유: 타일 기준으로 보면 매번 「어느 타일을 어디로?」를 판단해야 해서 규칙이 복잡해집니다. 반대로 빈칸 기준으로 보면 연산자가 상·하·좌·우 네 가지 안에서 딱 떨어집니다. 같은 문제라도 상태와 연산자를 어떻게 잡느냐에 따라 트리가 훨씬 단순해집니다.

초기 상태의 자식 노드 — 빈칸이 가운데이므로 자식이 4개

123 46 758

빈칸 ↑

13426758

빈칸 ↓

12345678

빈칸 ←

12346758

빈칸 →

12346758

네 자식 중 「빈칸 ↓」만이 가장 짧은 정답 경로 위에 있습니다. 여기서 다시 「빈칸 →」를 한 번 적용하면 목표 상태에 도달합니다. 깊이 2, 경로 비용 2.

여기서 배울 것

상태는 위치가 아니라 배치 전체일 수 있습니다. 노드 하나에 판 한 장이 통째로 들어갑니다.
상태 공간이 18개에서 181,440개로 뛰었습니다. 모두 확장해 보는 맹목적 탐색이 왜 한계에 부딪히는지 여기서 실감할 수 있습니다.
그래서 「목표까지 얼마나 남았을까」를 어림하는 값(휴리스틱)이 필요해집니다. 8-퍼즐에서는 제자리에 없는 타일의 개수나 각 타일이 제자리까지 가야 할 칸 수의 합을 씁니다.

n-Queen (4-Queen)

목표가 「경로」가 아니라 「최종 배치 그 자체」인 문제.

체스의 퀸은 가로·세로·대각선으로 원하는 만큼 움직입니다. 4×4 판에 퀸 4개를 서로 공격하지 못하게 놓는 것이 문제입니다. 퀸은 가로로도 공격하므로 한 행에 퀸이 둘일 수 없습니다. 그러면 「1행부터 차례대로 한 행에 하나씩 놓는다」로 문제를 다시 쓸 수 있고, 이 순간 트리가 만들어집니다.

① 상태	1행부터 몇 행까지 퀸을 놓았는지의 부분 배치. 각 행의 열 번호를 순서대로 적습니다. 가령 [2, 4] = 1행 2열, 2행 4열에 퀸이 있음.
② 초기 상태	빈 체스판 [ ]
③ 목표 상태	길이가 4이면서 서로 공격하지 않는 배치. [2, 4, 1, 3]이 그중 하나입니다.
④ 연산자	다음 빈 행의 1~4열 중 한 곳에 퀸을 놓기 (최대 4가지). 이미 놓인 퀸에게 공격받는 칸은 놓을 수 없습니다.
⑤ 경로 비용	의미가 없습니다. 어느 길로 가든 퀸을 4번 놓으면 끝이므로 모든 해답의 깊이가 같습니다.
상태 공간 크기	한 행에 하나씩 놓는 방식으로 4⁴ = 256가지의 완성 배치. 공격받는 칸을 미리 걸러 내면 실제로 만들어 보는 노드는 수십 개로 줄어듭니다.

상태 공간 트리 — 깊이 1칸이 곧 「한 행」

[ ] 빈 판

[1] ✗ 결국 실패 [2] ✓ 정답으로 [3] ✓ 정답으로 [4] ✗ 결국 실패

[2] 가지를 끝까지 따라가면

[2] → 2행에 놓기 → [2,4] → 3행에 놓기 → [2,4,1] → 4행에 놓기 → [2,4,1,3] 목표

2행에서 놓을 수 있는 열은 4열 하나뿐입니다. 1·2·3열은 모두 1행 2열의 퀸에게 공격받기 때문입니다. 규칙을 어기는 자식은 더 볼 필요가 없으므로 아예 만들지 않고 건너뜁니다. 탐색에서 빼는 때가 조금 이를 뿐, 이것도 가지치기입니다.

여기서 배울 것

탐색 문제에는 길을 찾는 문제(미로·8-퍼즐)와 조건을 만족하는 배치를 찾는 문제(n-Queen)가 있습니다. 후자는 경로가 아니라 잎 노드 자체가 답입니다.
따라서 「최단 경로」라는 말이 의미가 없습니다. 모든 해답의 깊이가 같기 때문입니다.
막다른 가지에서 이전 행으로 되돌아가 다른 열을 시도하는 것을 되추적(백트래킹)이라고 합니다.

다섯 문제 한눈에 비교하기

문제	상태	연산자	상태 공간 크기	답은 무엇인가
강 건너기	넷이 각각 어느 쪽 강가인지	농부가 하나를 데리고(또는 혼자) 건너기	16 (유효 10)	7번의 건너기 순서
미로	칸의 좌표 (행, 열)	상·하·좌·우 한 칸 이동	18	S에서 G까지의 경로
하노이의 탑	원판마다 어느 기둥인지	맨 위 원판을 다른 기둥으로	3ⁿ (n=3이면 27)	2ⁿ−1번의 이동 순서
8-퍼즐	아홉 칸의 배치 전체	빈칸을 상·하·좌·우로 이동	181,440	목표 배치까지의 이동 순서
n-Queen	1행부터의 부분 배치 [ … ]	다음 행에 퀸 하나 놓기	4⁴ = 256	잎 노드인 배치 자체

다섯 문제는 소재가 전혀 다르지만 표의 칸 이름은 하나도 바뀌지 않았습니다. 새로운 문제를 만났을 때도 똑같이 이 표를 채워 보세요. 표가 채워지면 그 문제는 이미 탐색 문제가 된 것입니다.

스스로 확인

8-퍼즐에서 연산자를 「타일을 옮긴다」가 아니라 「빈칸을 옮긴다」로 잡으면 무엇이 쉬워지나요? 4×4 판에 타일 15개를 놓는 15-퍼즐이라면, 빈칸을 옮기는 연산자는 한 상태에서 많아야 몇 가지일까요?

상태를 무엇으로 잡을 것인가

같은 문제인데 트리의 크기가 달라질 수 있을까?

앞의 다섯 탭에서 상태를 잡는 방식이 문제마다 달랐던 것을 기억해 보세요. 상태를 무엇으로 잡느냐는 주어지는 것이 아니라 우리가 정하는 것이고, 그 선택에 따라 트리의 크기가 크게 달라집니다.

같은 미로인데 트리를 훨씬 작게 만들 수도 있다

미로를 트리로 바꿀 때는 칸 하나를 상태 하나로 잡았습니다. 그런데 갈림길이 없는 복도에서는 갈 수 있는 곳이 어차피 하나뿐이라, 노드를 여러 개 만들어도 고를 것이 없습니다. 그래서 출발점 · 도착점 · 갈림길 · 막다른 곳만 상태로 잡고, 그 사이를 이어 준 복도는 간선 하나로 줄일 수 있습니다.

두 트리 모두 같은 미로를 옳게 나타낸 것입니다. 다만 오른쪽이 훨씬 작습니다. 대신 이때는 간선마다 몇 칸을 지나왔는지를 비용으로 적어 두어야 어느 길이 더 짧은지 비교할 수 있습니다. 상태를 무엇으로 잡느냐가 트리의 크기를 정합니다. 탐색을 설계할 때 가장 먼저 내려야 하는 판단이 이것입니다.

스스로 확인

갈림길만 상태로 잡아 트리를 줄이면, 대신 무엇을 함께 적어 두어야 어느 길이 더 짧은지 비교할 수 있나요?