Day 15 · 복습 · 그래프를 걸어가기

04 / RECALL & PRACTICE

기억에서 꺼내어 풀기

앞에서 풀었던 세 문제를 해설 없이 다시 풀어 보세요. 막히면 힌트를 열고, 풀이를 비교한 뒤 고친 점을 기록하세요.

문제 1

힌트 보기

첫 단계에서 큐는 [하린, 유나, 태오]가 됩니다. 하린을 꺼낼 때 지아와 서준이 들어갑니다.

풀이와 비교하기

방문 순서는 도윤, 하린, 유나, 태오, 지아, 서준, 보라, 민수입니다. 거리는 도윤 0, 하린·유나·태오 1, 지아·서준·보라 2, 민수 3입니다.

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

문제 2

힌트 보기

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 중에 이미 지나온 노드로 이어지는 엣지를 만나지 않습니다.

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

문제 3

힌트 보기

X(2)를 확정하면 Y가 5에서 2+1=3으로 줄어듭니다.

풀이와 비교하기

확정 순서는 S(0), X(2), Y(3), Z(5)입니다. X를 확정할 때 Y=3, Z=8이 되고, Y를 확정할 때 Z가 3+2=5로 줄어듭니다. 최단 경로는 S→X→Y→Z, 비용은 5입니다.

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

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

세 문제를 푼 뒤 핵심 개념 펼치기

큐로 층층이, 스택으로 깊이, 확정과 완화로 가중치까지 다룹니다. 세 탐색이 언제 같은 답을 내고 언제 다른 답을 내는지 확인합니다.

BFS는 큐로 가까운 노드부터 방문하며, 가중치가 없는 그래프에서 처음 붙인 거리가 최단 홉 거리입니다.

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

다익스트라는 거리가 가장 작은 미확정 노드를 확정하고 이웃을 완화하는 일을 반복해, 음수가 없는 가중 그래프의 최단 경로를 찾습니다.

BFS·큐·거리 · DFS·스택·되돌아가기 · 다익스트라·완화를 연결해 설명해 보세요.

05 / CHECK YOURSELF

모든 엣지 가중치가 1인 그래프에서 다익스트라가 확정하는 거리와 항상 같은 값은?

완료 조건: 확인 퀴즈 정답 · / 직접 풀기 0/3

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