Day 12 · 깊이 우선 탐색

A SMALL DETOUR

이번 회차, 내 속도로.

기초를 더 짚거나 궁금한 주제로 잠깐 넓혀 보세요. 최대 3단계를 거쳐 DAY 12로 돌아옵니다.

난이도·관심 주제 고르기

이번 회차는 어느 속도로 볼까요?기초부터새 보충 수업부터 짚어요현재 수준으로관심 주제부터 살펴봐요한 걸음 더새 심화 수업까지 넓혀요

더 살펴볼 주제 1~2개 선택FIFO·LIFO·방문 표시추가 05 · 새 수업 · 11·12회차에서 큐와 스택의 상태 변화가 헷갈렸다면, 작은 나무 모양 그래프로 한 줄씩 따라가 봅니다.f = g + h·허용 휴리스틱추가 06 · 새 수업 · 13회차의 다익스트라를 마친 뒤, 도착점이 정해져 있을 때 확정할 노드 수를 줄이는 방법을 봅니다.BFS·큐·거리DAY 11 · 큐로 층층이 넓혀 가는 BFS가 최단 홉 거리를 주는 이유를 다시 확인합니다.다익스트라·완화DAY 13 · 가중치가 있을 때 확정과 완화로 최단 경로를 찾는 과정을 손으로 따라갈 수 있습니다.홉 거리·지름·작은 세상DAY 14 · 평균 경로 길이와 지름으로 몇 단계면 닿는지 재고, 지름길이 거리를 줄이는 효과를 봅니다.*1..3·shortestPathDAY 33 · Cypher의 가변 길이 패턴과 shortestPath가 BFS의 홉 거리와 같은 질문을 쿼리로 묻는 방법임을 확인합니다.

1/2개 선택 · 새 보충·심화 수업과 본과정 다시 읽기를 선택할 수 있어요.

이렇게 다녀와요 1단계 · 약 12분

출발 · DAY 12DFS·스택·되돌아가기
1. 관심 주제FIFO·LIFO·방문 표시추가 05 · 새 추가 수업
복귀 · DAY 12원래 회차 이어가기

FIFO·LIFO·방문 표시 · 11·12회차에서 큐와 스택의 상태 변화가 헷갈렸다면, 작은 나무 모양 그래프로 한 줄씩 따라가 봅니다.

선택과 경로 기록은 이 브라우저에 저장됩니다. 본과정의 회차 완료와는 별도입니다.

복귀: DAY 12 → 본과정 다음 회차: DAY 13

01 / UNDERSTAND

핵심 개념

깊이 우선 탐색(depth-first search, DFS)은 현재 노드의 이웃 중 아직 가 보지 않은 노드 하나로 바로 들어갑니다. 더 갈 곳이 없으면 직전 노드로 되돌아가(backtracking) 남은 이웃을 확인합니다. 미로에서 한쪽 벽을 짚고 막다른 곳까지 가 본 뒤 갈림길로 돌아오는 방식과 비슷합니다.

되돌아갈 곳을 기억하는 도구가 스택(stack)입니다. 스택은 나중에 넣은 것을 먼저 꺼내는 더미(LIFO)입니다. 들어갈 때 노드를 스택에 쌓고, 막히면 맨 위를 꺼내 그 아래 노드로 돌아갑니다. 함수가 자기 자신을 부르는 재귀(recursion)로 구현해도 컴퓨터가 내부에서 같은 방식의 스택을 씁니다.

같은 출발점이라도 DFS와 BFS의 방문 순서는 다릅니다. DFS가 어떤 노드에 처음 도착했을 때의 깊이는 최단 거리가 아닐 수 있으므로 거리 계산에는 BFS를 씁니다. 대신 DFS는 지금 걷는 길을 스택으로 알고 있어서, 직전 노드가 아닌데 그 길 위에 있는 노드로 이어지는 엣지를 만나면 사이클이 있다는 것을 알아챕니다. 타잔(Tarjan, 1972)은 DFS로 강한 연결 요소 같은 구조를 그래프 크기에 비례하는 시간에 찾는 방법을 보였고, 방향 그래프에서 작업 순서를 정하는 위상 정렬(topological sort)도 DFS로 흔히 구현합니다.

DFS는 스택으로 한 갈래를 끝까지 따라갔다가 되돌아오며, 방문 순서는 BFS와 다르고 사이클 탐지에 쓰입니다.

02 / WORKED EXAMPLE∑

작은 예제로 따라가기

하린에서 시작해 이웃 목록 순서대로 들어가면 하린 → 지아 → 민수 → 서준입니다. 서준에서 하린으로 가는 엣지는 지금 걷는 길 위의 하린으로 돌아가므로 사이클(하린–지아–민수–서준–하린)이 있다는 신호입니다.

서준에서 더 갈 곳이 없어 민수, 지아를 거쳐 하린까지 되돌아온 뒤, 하린의 남은 이웃 도윤으로 들어가 도윤 → 유나 → 태오 → 보라 순서로 방문합니다.

DFS 순서는 하린, 지아, 민수, 서준, 도윤, 유나, 태오, 보라입니다. 같은 출발점의 BFS 순서는 하린, 지아, 서준, 도윤, 민수, 유나, 태오, 보라로, BFS는 도윤을 네 번째에, DFS는 민수까지 깊이 들어간 뒤 다섯 번째에 만납니다.

03 / EXPLORE

직접 실험해 보기

시작 노드를 고르고 ‘다음 단계’로 스택이 쌓이고 줄어드는 모습과 되돌아가는 순간의 강조를 확인한 뒤, ‘BFS 순서 비교’를 골라 두 방문 순서를 나란히 비교하세요.

LIVE EXPERIMENT · DFS

DFS로 한 갈래 끝까지 갔다가 되돌아오기

스택 맨 위(현재)스택 안의 경로되돌아가는 중

0단계 · 깊이 들어가기하린을(를) 스택에 넣고 방문 (#1)

스택 (아래 → 위)

하린

스택 맨 위 노드의 이웃 중 가나다 순으로 첫 미방문 노드로 들어가고, 없으면 꺼내서 되돌아갑니다.

04 / RECALL & PRACTICE

이번에는 직접 풀어 보세요

정답을 보기 전에 계산과 이유를 적어 보세요. 해설과 비교하고 확인 표시를 남기면 완료할 수 있습니다.

문제 1

노드 1~6과 엣지 1–2, 1–3, 2–4, 2–5, 3–6이 있습니다(이웃은 번호 순). 1에서 DFS와 BFS를 각각 돌려 방문 순서를 적고, DFS에서 처음으로 되돌아가는 지점을 표시하세요.

힌트 보기

DFS는 1→2→4로 들어간 뒤 4에 새 이웃이 없어 막힙니다. BFS는 거리 1인 2와 3을 먼저 모두 방문합니다.

풀이와 비교하기

DFS는 1, 2, 4, (4에서 2로 되돌아감) 5, (2를 거쳐 1로 되돌아감) 3, 6입니다. BFS는 1, 2, 3, 4, 5, 6입니다. 이 그래프는 사이클이 없는 나무 모양이라 DFS 중에 이미 지나온 노드로 이어지는 엣지를 만나지 않습니다.

내 풀이를 해설과 비교하고 다른 점을 확인했어요.

풀이와 확인 표시는 이 브라우저에 저장됩니다.

이 자료는 개념 학습용입니다. 실제 데이터베이스·라이브러리·플랫폼의 동작과 설정은 제품과 버전마다 다를 수 있습니다.

깊이 우선 탐색