- 문제 해결을 '상태 공간에서의 탐색'으로 표현하고, 탐색의 중요성을 설명할 수 있다.
- 맹목적 탐색(BFS·DFS)의 원리와 한계를 설명할 수 있다.
- 맹목적 탐색과 정보 이용 탐색의 차이를 휴리스틱을 중심으로 설명할 수 있다.
생각 열기 — 미로 속 두 사람
거대한 미로에 갇힌 두 사람을 상상해 보세요. 첫 번째 사람은 출구가 어딘지 전혀 몰라 갈림길마다 무작정 한쪽씩 다 들어가 봅니다. 두 번째 사람은 멀리 출구 위의 빛이 보여서, 갈림길마다 빛에 더 가까워지는 쪽을 골라 갑니다. 누가 먼저 빠져나올까요?
이 차이가 바로 오늘의 주제예요. 첫 번째는 맹목적 탐색, 두 번째는 정보 이용 탐색. 인공지능이 '똑똑하게' 길을 찾는 비결이 바로 저 '빛' — 휴리스틱에 있습니다.
두 번째 사람의 '빛을 향해 가기' 전략이 항상 최선일까요? 빛 쪽으로 갔는데 거기가 막다른 벽이라면 어떻게 될까요? 이 질문을 기억해 두세요 — 오늘 시뮬레이터에서 직접 답을 보게 됩니다.
모든 문제는 '탐색'이 될 수 있다
상태 공간이라는 지도
인공지능은 문제를 풀기 위해 먼저 문제를 '상태'와 '행동'으로 바꿔 표현해요. 상태 공간이라고 합니다.
상태(state)
문제의 한 순간. 미로에서는 '내가 서 있는 칸', 퍼즐에서는 '조각들의 배치'예요.
행동(action)
상태를 바꾸는 한 걸음. 미로에서는 '상하좌우 이동', 길찾기에서는 '다음 교차로로'예요.
목표(goal)
도달하려는 상태. 미로의 출구, 퍼즐의 완성된 모습이에요.
그러면 문제 풀이는 "시작 상태에서 출발해, 행동을 이어 붙여 목표 상태에 닿는 길을 찾는 일"이 됩니다. 이것이 바로 탐색(search)이에요. 길찾기·퍼즐 맞추기·게임의 다음 수 두기·일정 짜기까지, 놀랄 만큼 많은 문제가 탐색으로 표현됩니다.
탐색이 중요한 이유는, 상태의 수가 상상을 초월할 만큼 많기 때문이에요. 바둑판 위에서 가능한 배치는 우주의 원자 수보다 많습니다(약 10170가지!). 이 모든 경우를 일일이 다 둘러보는 건 슈퍼컴퓨터로도 불가능하죠. 그래서 '얼마나 적은 상태만 살펴보고도 답을 찾느냐'가 인공지능의 핵심 능력이 됩니다 — 바로 그래서 '똑똑한 탐색'이 필요한 거예요.
맹목적 탐색 — 목표가 어딘지 모른 채 뒤지기
너비 우선(BFS)과 깊이 우선(DFS)
맹목적 탐색(무정보 탐색)은 목표가 어느 방향에 있는지 전혀 모른 채, 정해진 규칙대로 상태를 하나씩 펼쳐 보는 방법이에요. 대표적인 두 가지가 있습니다.
너비 우선 탐색 (BFS)
시작점에서 가까운 곳부터 차근차근 물결처럼 펼쳐 가요. 칸 수가 같은 미로라면 항상 최단 경로를 찾지만, 둘러보는 칸이 많아요.
깊이 우선 탐색 (DFS)
한 방향으로 끝까지 파고들다 막히면 되돌아와 다른 길을 시도해요. 운이 좋으면 빠르지만, 최단 경로를 보장하지 않아요.
정보 3단원에서 배운 순차·이진 탐색이 '한 줄로 늘어선 데이터'를 찾는 것이었다면, 여기서는 갈림길이 있는 지도(그래프)를 탐색합니다. 공통점은 둘 다 '체계적으로 빠짐없이 찾기'라는 점이에요.
정보 이용 탐색 — 목표 쪽으로 눈치껏
휴리스틱이라는 '나침반'
정보 이용 탐색(정보 탐색)은 목표가 어느 쪽인지에 대한 힌트를 활용해, 목표에 더 가까워 보이는 쪽을 먼저 살펴보는 방법이에요. 이때 쓰는 '힌트', 즉 목표까지의 거리에 대한 어림짐작을 휴리스틱(heuristic)이라고 합니다.
예를 들어 미로에서 '목표 칸까지의 직선 거리'를 휴리스틱으로 쓰면, 갈림길마다 목표에 더 가까워지는 칸을 먼저 골라 갈 수 있어요. 생각 열기의 '빛을 향해 가는 사람'이 바로 이 방식입니다. 둘러보는 칸이 훨씬 적어 대개 빠르죠. 다만 앞서 던진 질문 — "빛 쪽이 막다른 길이면?"의 함정도 있어요. 직접 확인해 봅시다.
🟢 출발에서 🔴 목표까지! 세 가지 방법이 어떻게 탐색하는지 비교하세요. 연한 보라색은 '둘러본 칸', 노란색은 '찾아낸 경로'예요. 칸을 클릭하면 벽을 세우거나 없앨 수 있어요(드래그도 OK).
대개 정보 이용 탐색(휴리스틱)이 가장 적은 칸만 둘러보고 목표를 찾아요 — '나침반'이 있으니까요. 하지만 함정도 보입니다. 탐욕적으로 목표 방향만 좇다 보면 최단 경로가 아닌 길로 돌아갈 수 있어요(빛 쪽이 막다른 길이었던 경우!). 반면 BFS는 둘러보는 칸은 많아도 항상 최단 경로를 보장하죠. "빠르게 찾기"와 "최선을 보장하기" 사이의 이 줄다리기를 똑똑하게 해결하는 방법이 다음 시간의 A* 알고리즘입니다!
| 비교 기준 | 너비 우선(BFS) | 깊이 우선(DFS) | 정보 이용(휴리스틱) |
|---|---|---|---|
| 목표 위치 힌트 | 없음(맹목적) | 없음(맹목적) | 있음(휴리스틱) |
| 둘러보는 칸 수 | 많음 | 경우에 따라 | 대체로 적음 |
| 최단 경로 보장 | 예(가중치 같을 때) | 아니요 | 아니요(탐욕적) |
| 메모리 사용 | 많음 | 적음 | 중간 |
확인 문제
바로바로 채점!
2차시 확인 문제
4문항 · 즉시 채점
1인공지능에서 '탐색(search)'을 가장 잘 설명한 것은?
2맹목적 탐색과 정보 이용 탐색의 결정적 차이는?
3휴리스틱(heuristic)에 대한 설명으로 옳은 것은?
4[OX] 정보 이용 탐색(휴리스틱)은 항상 최단 경로를 보장한다.
더 알아보기
교과서 너머의 이야기 — 클릭해서 펼쳐 보세요
연계정보 3단원의 탐색 vs 이 단원의 탐색
정보 과목 3단원에서 배운 순차 탐색·이진 탐색과 지금의 탐색은 '찾기'라는 점은 같지만 무대가 달라요. 정보 3단원은 한 줄로 늘어선 데이터(리스트)에서 특정 값을 찾았다면, 여기서는 갈림길이 있는 지도(그래프)에서 목표까지의 '길'을 찾습니다. 그래서 단순히 '찾았다/못 찾았다'가 아니라 '어떤 경로로 갔는가'가 중요해지죠. 이진 탐색이 '정렬'이라는 추가 정보를 활용해 빨라졌듯, 정보 이용 탐색은 '휴리스틱'이라는 추가 정보로 빨라집니다 — 좋은 정보가 탐색을 빠르게 한다는 교훈은 두 단원에 공통이에요!
심화좋은 휴리스틱의 조건 — '욕심내되 과장하지 마라'
휴리스틱이라고 다 같은 게 아니에요. 좋은 휴리스틱은 두 조건을 지켜요. ① 실제 남은 거리보다 부풀리지 않기 (이를 '허용 가능하다(admissible)'고 해요). 예를 들어 '직선거리'는 실제 길보다 절대 멀 수 없으니 안전한 휴리스틱이죠. 만약 휴리스틱이 실제보다 과장되면, 진짜 최단 경로를 놓칠 수 있어요. ② 계산이 빨라야 해요 — 힌트 하나 구하는 데 오래 걸리면 배보다 배꼽이 크니까요. 미로에서 자주 쓰는 휴리스틱은 맨해튼 거리(가로 칸 차이 + 세로 칸 차이)와 직선거리예요. 다음 시간 A* 알고리즘이 바로 이 '허용 가능한 휴리스틱'을 활용해 '빠르면서도 최단 경로를 보장하는' 마법을 부립니다!
사례게임 속 몬스터는 어떻게 나를 쫓아올까
게임에서 적 캐릭터(NPC)가 장애물을 피해 플레이어에게 다가오는 것, 당연해 보이지만 사실은 매 순간 경로 탐색(pathfinding)이 돌아가는 거예요. 대부분의 게임은 맵을 격자나 그래프로 나누고 A* 알고리즘(다음 시간!)으로 플레이어까지의 길을 찾습니다. 캐릭터가 갑자기 벽에 끼거나 엉뚱한 길로 가는 '버그'는 대개 이 경로 탐색이 꼬인 거랍니다. 길찾기 내비게이션, 물류 로봇의 창고 이동, 택배 배송 경로 최적화까지 — 오늘 배운 탐색은 화면 곳곳에서 쉬지 않고 일하고 있어요. 다음 시간에는 이 모든 것의 왕, A* 알고리즘을 직접 조종해 봅니다!