236. 상태 공간 탐색 (DFS / BFS)

핵심 인사이트 (3줄 요약)

본질: 상태 공간 트리(State Space Tree)는 인공지능이 퍼즐이나 미로를 풀 때, **"내가 여기서 선택할 수 있는 모든 경우의 수(상태)를 점(Node)으로 찍고, 선택의 흐름을 선(Edge)으로 연결해 우주 끝까지 뻗어나가는 거대한 족보(Tree) 그래프"**를 그려 정답을 찾는 노가다 탐색법이다.

가치: 이 거대한 족보를 다 뒤지는 건 불가능하므로 AI는 탐색 전략을 짠다. **깊이 우선 탐색(DFS)**은 "한 우물만 끝까지 파고, 막히면 돌아오자"는 무식하지만 메모리(RAM)를 적게 먹는 전략이고, **너비 우선 탐색(BFS)**은 "안전하게 1층 다 뒤지고, 2층 다 뒤지자"며 최단 거리 정답을 100% 보장하지만 메모리가 미친 듯이 터져나가는 전략이다.

판단 포인트: 바둑이나 체스처럼 경우의 수가 우주의 원자 수($10^{170}$)보다 많은 게임에서는 BFS를 켜는 순간 1초 만에 서버가 OOM(메모리 초과)으로 죽어버린다. 시스템의 가용 메모리 한계와 탐색 트리의 깊이(Depth)에 따라 DFS와 BFS를 저울질하거나 섞는 것(IDS)이 탐색 알고리즘 아키텍트의 기본 소양이다.

Ⅰ. 개요 및 필요성

초창기 인공지능(1960년대)은 딥러닝처럼 사진을 보고 개/고양이를 구분하는 게 아니었다. AI의 지능을 뽐내는 유일한 무대는 체스, 8퍼즐(숫자 밀어 맞추기), 하노이의 탑 같은 '게임'이었다. 기계가 체스를 이기려면 어떻게 해야 할까? 직관? 딥러닝? 다 필요 없고, **"내가 돌을 여기 놨을 때 일어날 수 있는 미래의 모든 경우의 수를 수백만 개 그려보고, 가장 이길 확률이 높은 길을 고르는 노가다 계산"**이 정답이었다.

이 '경우의 수' 하나하나를 점(State)으로 부르고, 점들을 가지치기하며 뻗어나가는 지도를 **상태 공간 트리 (State Space Tree)**라고 부른다. 맨 꼭대기 점은 '현재 체스판의 상태(초기 상태)'고, 맨 밑바닥 점 어딘가에는 '내가 체스에서 이긴 상태(목표 상태)'가 숨어 있다.

문제는 이 지도가 너무 거대하다는 것이다. 8퍼즐만 해도 점(경우의 수)이 36만 개고, 바둑은 $10^{170}$개다. 이 미치도록 넓고 깊은 우주에서 AI가 '정답(목표 상태)'을 찾아 미로를 헤매는 맹인 탐색(Blind Search)의 가장 기본이 되는 두 가지 엔진이 바로 밑바닥으로 직진하는 **깊이 우선(DFS)**과 옆으로 퍼져나가는 너비 우선(BFS) 알고리즘이다.

📢 섹션 요약 비유: 상태 공간 트리는 '수능 객관식 찍기 경우의 수 지도'다. 1번 문제에서 1~5번을 찍는 5갈래 길이 생기고, 2번 문제에서 또 5갈래가 생겨 25갈래가 된다. 이 수백만 개의 갈래 끝 어딘가에 '100점(목표 상태)'이라는 방이 하나 있다. AI는 눈을 감은 채 이 미로 속 방의 문을 열고 들어가서 100점 방을 찾아내는 무식하지만 확실한 미로 탐험가다.

Ⅱ. 아키텍처 및 핵심 원리

AI가 상태 공간 트리를 뒤질 때 머릿속의 임시 저장소(자료구조)를 스택(Stack)으로 쓰냐 큐(Queue)로 쓰냐에 따라 맹인 탐색의 경로가 완전히 정반대로 갈라진다.

┌──────────────────────────────────────────────────────────────┐
│           상태 공간 탐색: 깊이 우선(DFS) vs 너비 우선(BFS) 아키텍처 도해 │
├──────────────────────────────────────────────────────────────┤
│  [거대한 상태 공간 트리(Tree)]                                      │
│         (A) 시작 노드 (1층)                                     │
│        /   \                                                 │
│      (B)   (C)       (2층)                                     │
│     /  \   /  \                                              │
│   (D) (E) (F) (G)    (3층)     ※ 목표 노드는 (F)라고 가정!         │
│                                                              │
│  [1. 깊이 우선 탐색 (DFS, Depth-First Search) - 외길 직진 멧돼지]    │
│   * 사용 자료구조: Stack (스택, 후입선출 - 마지막에 본 곳부터 다시 파기)  │
│   * 탐색 순서: A ─▶ B ─▶ D (끝까지 파봄, 꽝!) ─▶ 백트래킹(뒤로 빽!)    │
│            ─▶ E (꽝!) ─▶ 백트래킹 ─▶ C ─▶ F (정답 발견! 빙고!)   │
│   * 장점: 기억(메모리)해야 할 갈림길이 몇 개 없어서 RAM 소모가 미미함.    │
│   * 단점: 운 나쁘면 정답은 바로 옆(C)에 있는데, 영원히 끝이 없는 D 밑바닥 │
│          블랙홀로 빠져 영원히 못 돌아올 수 있음 (무한 루프 붕괴).      │
│                                                              │
│  [2. 너비 우선 탐색 (BFS, Breadth-First Search) - 안전제일 탐험대]   │
│   * 사용 자료구조: Queue (큐, 선입선출 - 줄 선 순서대로 평등하게 수색)   │
│   * 탐색 순서: A (1층 끝) ─▶ B ─▶ C (2층 다 뒤짐)                  │
│            ─▶ D ─▶ E ─▶ F (정답 발견! 빙고!)                  │
│   * 장점: 가장 얕은 층에 있는 '최단 거리 정답'을 무조건 100% 보장함!    │
│   * 단점: 10층을 뒤지려면 1~9층의 모든 점(수십억 개)을 몽땅 RAM에 저장해 │
│          둬야 해서 메모리가 우주 폭발함 (OOM 사망).               │
└──────────────────────────────────────────────────────────────┘

핵심 원리 (Stack vs Queue의 메모리 딜레마): DFS는 메모리(RAM)를 아주 조금 먹는다. 지금 내가 걸어 들어온 길(Path)만 스택에 저장해 두고 막히면 한 칸 뒤로 물러서기(Backtracking) 때문이다. 깊이가 100층이어도 100개의 점만 기억하면 된다(공간 복잡도 선형). 반면 BFS는 큐(Queue)에 같은 층의 모든 형제 노드들을 와르르 욱여넣고 동시에 전진한다. 층이 깊어질수록 기억해야 할 점의 수가 지수 함수($2^n$, $3^n$)로 폭발하여, 정답을 찾기도 전에 컴퓨터 메모리가 가득 차서 프로그램이 강제 종료(OOM)되어 버리는 끔찍한 공간 복잡도의 저주에 빠진다.

📢 섹션 요약 비유: DFS(깊이 우선)는 '다이아몬드 광산 파기'다. 땅을 파다가 안 나오면 끝까지 우물을 파본다. 운 좋게 다이아몬드를 빨리 찾으면 대박이지만, 운 나쁘면 지구 내핵까지 파고 들어가서 영원히 못 돌아온다(무한 루프). BFS(너비 우선)는 '경찰의 산악 수색대'다. 100명이 일렬로 서서 산의 입구(1층)부터 10m씩 꼼꼼하게 산 전체를 평등하게 훑고 올라간다. 무조건 시체를 찾지만, 산이 너무 크면 수색대원(메모리)이 수억 명이 필요해서 경찰청 예산(RAM)이 파산한다.

Ⅲ. 비교 및 연결

미로의 구조(트리의 형태)와 컴퓨터의 하드웨어 스펙(RAM 용량)을 보고, 아키텍트는 둘 중 하나를 칼같이 골라야 한다.

탐색 알고리즘	탐색 철학 및 핵심 전략	가장 유리한 상황 (Pros)	치명적인 붕괴 상황 (Cons)
DFS (깊이 우선 탐색)	일단 가장 깊은 곳까지 뚫고 본다. (외골수 직진)	미로의 정답이 아주 깊은 밑바닥에 숨어있을 때 압도적으로 빨리 찾음. 메모리 제약 0% 수준.	트리의 깊이가 '무한대'인 곳에서 잘못된 길로 빠지면, 영원히 안 끝나는 블랙홀(Infinite Loop)에 갇혀버림. 최단 거리 보장 불가.
BFS (너비 우선 탐색)	얕은 층부터 평등하게 싹 다 뒤지며 내려간다. (안전제일)	정답이 시작점에서 가까운 얕은 층에 있을 때 바로 낚아챔. '최단 거리' 정답을 100% 무조건 보장함.	트리가 가지가 많은(분기 계수 Branching Factor가 큰) 게임에서 메모리 오버플로우(OOM)로 서버 즉사.
IDS (반복적 깊이 심화 탐색)	DFS와 BFS를 섞은 끔찍한 짬뽕 (Iterative Deepening Search).	1층까지만 DFS로 파보고, 없으면 2층까지만 DFS로 파보고, 없으면 3층 제한 걸고 DFS를 다시 함!	DFS의 장점(메모리 안 터짐)과 BFS의 장점(최단 거리 100% 보장)을 모두 갖춘 맹인 탐색의 마스터피스! 단, 위층을 반복해서 계속 파야 하므로 시간이 약간 낭비됨.

최근 코딩 테스트나 실무 길 찾기 알고리즘에서는 BFS와 DFS라는 맹인 탐색(아무 힌트 없이 무지성으로 다 뒤짐)을 거의 쓰지 않는다. "지도상으로 여기가 더 정답이랑 가까워 보이네!"라는 눈치(Heuristic)를 더한 A (에이 스타) 알고리즘*이나 언덕 오르기 탐색 같은 진보된 정보 기반 탐색으로 넘어가는 것이 기본 테크 트리다.

📢 섹션 요약 비유: 집에 숨겨둔 비상금을 찾는다고 치자. DFS는 안방 장롱을 열면, 장롱 안의 서랍, 그 안의 상자, 그 안의 봉투까지(깊이) 끝까지 싹 다 뒤져야만 거실로 넘어가는 아빠다. 정답이 얕은 거실 소파 위에 있다면 아빠는 평생 장롱만 파다가 못 찾는다. BFS는 거실의 모든 서랍 1층, 안방의 모든 서랍 1층을 다 열어보고, 그제야 2층을 열어보는 꼼꼼한 엄마다. 비상금이 소파 위에 있으면 1초 만에 최단 거리로 낚아채지만, 집이 너무 넓으면 열어둔 서랍(메모리)을 기억 못 해 뇌가 과부하 된다. IDS(짬뽕)는 엄마의 꼼꼼함과 아빠의 파고드는 스킬을 완벽하게 섞어놓은 탐정이다.

Ⅳ. 실무 적용 및 기술사 판단

게임 AI 엔진을 만들거나 내비게이션 라우팅을 짤 때, 무지성으로 DFS나 BFS의 기본 내장 함수를 호출하면 서버가 무한 루프에 빠져 아키텍트의 모가지가 날아간다.

실무 아키텍처 판단 (체크리스트)

무한 루프 방어선 (Visited Array / Closed List) 하드코딩: DFS의 가장 치명적인 결함은 '내가 지나온 길(Cycle)'을 빙글빙글 계속 도는 것이다. A $\rightarrow$ B $\rightarrow$ C $\rightarrow$ A로 이어지는 미로에서, 지나온 흔적을 체크하지 않으면 DFS는 우주가 끝날 때까지 저 4개의 방을 맴돌며 전력을 낭비한다. 탐색을 짤 때는 무조건 **'방문한 노드(Visited Array)'**라는 거대한 체크리스트 DB(Hash Set)를 옆에 띄워두고, "어? 나 아까 C방 와봤는데? 그럼 다시 안 들어가고 스킵(Pruning)!"이라는 백트래킹(Backtracking) 강제 커트라인을 무조건 코딩해야 한다.
트리 깊이 제한 (Depth Limit) 설정의 딜레마: 바둑(경우의 수 $10^{170}$)에서 끝까지 파고드는 DFS를 쓴다는 건 미친 짓이다. 1수를 둘 때 게임이 끝날 때까지 수만 수를 계산할 순 없다. 체스나 바둑 AI(미니맥스 등)를 짤 때는 무조건 **"지금부터 딱 5수 앞(Depth Limit = 5)까지만 파고들고 무조건 멈춰서 빠져나와라!"**라는 제한을 걸어야 실시간(Real-time) 플레이가 가능하다. 깊이 제한에서 멈췄을 때, 그 상태가 얼마나 유리한지 대충 평가하는 함수(Evaluation Function)를 결합하는 것이 게임 트리 탐색의 핵심이다.

안티패턴

가중치 그래프(Weighted Graph)에 대한 BFS 맹신 버그: 내비게이션 길 찾기를 짤 때, 도로마다 톨게이트 비용이나 막히는 시간(가중치)이 다른데 무지성 BFS(너비 우선 탐색)를 돌려버리는 끔찍한 오판. BFS는 오직 "방을 몇 번 거쳤는가(단순 노드 점프 횟수)" 기준으로 최단 거리를 뽑아낸다. BFS에 톨게이트 데이터를 넣고 돌리면, "서울 $\rightarrow$ 부산" 직통 고속도로(요금 10만 원)가 "서울 $\rightarrow$ 대전 $\rightarrow$ 대구 $\rightarrow$ 부산" 국도(요금 1만 원)보다 점프 횟수가 1번으로 더 적다며 10만 원짜리 최악의 길을 '최단 거리'라고 뱉어내는 멍청한 짓을 한다. 가중치가 섞인 도로망에서는 BFS를 폐기하고 무조건 다익스트라(Dijkstra)나 A 알고리즘*을 꺼내 들어야 한다.
📢 섹션 요약 비유: 가중치 무시 BFS 버그는 '경유지 개수만 세는 비행기 예약'과 같다. 미국 갈 때, 직항(점프 1번, 500만 원) 비행기와, 일본 $\rightarrow$ 하와이 $\rightarrow$ 미국 경유(점프 3번, 50만 원) 비행기가 있다. 짠돌이 배낭여행객(가중치 그래프)에게는 당연히 50만 원짜리 경유가 최단(최적) 루트다. 그런데 BFS 여행사 직원은 돈(가중치)은 신경도 안 쓰고 무조건 점프 횟수가 적은(얕은 층) 500만 원짜리 표를 "가장 짧은 길입니다!"라며 결제해 버리는 참사를 빚는다. 현실 세계는 돈과 시간(가중치)의 싸움이므로 멍청한 노드 개수 세기(BFS)는 안 통한다.

Ⅴ. 기대효과 및 결론

상태 공간 탐색(State Space Search)의 양대 산맥인 DFS와 BFS는 인공지능이 인간의 **'시행착오(Trial and Error)'**라는 지적 능력을 컴퓨터의 RAM과 CPU 코드로 완벽하게 번역해 낸 최초의 논리적 굴착기다.

딥러닝이 아무리 발전해도 세상의 모든 문제를 '확률'로만 찍어 맞출 수는 없다. 지하철 노선도의 최단 환승 경로를 찾거나, 반도체 회로의 꼬이지 않는 배선 길을 찾는(Routing) 완벽하게 정밀한 문제 앞에서는, 결국 컴퓨터가 묵묵히 수만 개의 경우의 수(State)를 트리로 전개하고 끝까지 파헤쳐보는 무식한 탐색 알고리즘(Search Algorithm)의 땀방울이 필요하다. DFS와 BFS는 이 고된 노가다의 가장 견고한 기초 공사 도구다.

이제 AI 아키텍처는 이 맹인 탐색(눈 감고 다 뒤지기)의 한계를 넘어섰다. BFS의 안전함에, 목적지 쪽으로 빛을 비춰주는 등대(휴리스틱)를 꽂아 길을 잃지 않게 한 A (에이 스타) 알고리즘*이 탄생했고, 바둑판의 미친 무한대 경우의 수를 뚫기 위해 랜덤하게 아무 곳이나 찔러보고 승률을 계산하는 **몬테카를로 트리 탐색(MCTS - 알파고의 심장)**으로 찬란하게 진화했다. 하지만 그 모든 첨단 AI 탐색 엔진의 DNA 깊숙한 곳에는, 미로의 왼쪽 벽을 끝까지 짚어가며(DFS) 정답을 향해 기어가는 고전적 인공지능의 투지가 여전히 펄떡이고 있다.

📢 섹션 요약 비유: DFS와 BFS는 인공지능의 '구구단'이자 '근력 운동'이다. 구구단(기본 탐색)을 못 외우면 미적분(딥러닝, 알파고)을 쳐다볼 수도 없다. 알파고가 바둑돌을 둘 때 수조 개의 경우의 수를 헤쳐 나가는 화려한 스텝(MCTS)의 껍질을 다 벗겨내고 나면, 결국 그 가장 깊은 바닥에는 "이 길로 끝까지 가볼까?(DFS)"와 "옆 길도 다 한번 둘러볼까?(BFS)"라는 두 가지 원초적 본능만이 남아 인공지능의 심장을 돌리고 있는 것이다.

📌 관련 개념 맵

개념	연결 포인트
백트래킹 (Backtracking)	DFS(깊이 우선 탐색)의 단짝 친구. 우물을 끝까지 팠는데 정답이 없으면 쿨하게 흙을 털고 "아까 지나친 갈림길로 다시 뒤로 빽(Back)해서 다른 길을 파자!"라고 돌아가는 핵심 퇴각 기술
Heuristic (휴리스틱 / 눈치 탐색)	DFS, BFS처럼 눈 감고 다 뒤지는 무식한 맹인 탐색(Blind Search)을 졸업하고, "저기서 고기 냄새가 나니까 저쪽 샛길부터 파보자!"라고 인간의 직감을 수식으로 만들어 탐색 속도를 100배 올리는 업그레이드 마법
A 알고리즘 (에이 스타)*	게임 캐릭터 길 찾기(Pathfinding)의 전 세계 표준. 목적지와의 직선거리(눈치, Heuristic)와 지금까지 걸어온 비용(가중치)을 동시에 계산해 내는 BFS의 궁극적 최종 진화 형태
상태 공간 트리 (State Space Tree)	현재 체스판의 말 위치(초기 상태)에서 시작해, 내가 이길 때(목표 상태)까지 나올 수 있는 세상의 모든 경우의 수(상태)들을 동그라미와 선으로 거대하게 그려놓은 인공지능의 보물지도

👶 어린이를 위한 3줄 비유 설명

캄캄한 미로 속에서 보물을 찾아야 해요! 상태 공간 트리는 내가 미로에서 갈 수 있는 모든 갈림길을 그림으로 쫙 그려놓은 거대한 지도예요.
DFS (깊이 우선) 친구는 "무조건 한 우물만 파!" 라면서 한쪽 길로 끝까지 다다닥 뛰어가서 찾아보는 저돌적인 탐험가예요. (기억할 게 별로 없어서 편해요)
BFS (너비 우선) 친구는 "안전이 최고지!" 라면서 미로의 1층을 다 열어보고, 그다음 2층을 꼼꼼히 다 열어보는 꼼꼼한 엄마예요. (가장 빠른 길을 100% 보장하지만 머리가 엄청 아파요)