미로와 도로 지도에서 경로 찾기가 달라지는 이유
몇 칸인지, 요금이 얼마인지, 모든 지점 사이의 거리가 필요한지에 따라 문제가 달라집니다. 방문한 칸과 최종 경로를 서로 다른 정보로 읽으세요.
툴허브 편집 ·
층별 탐색과 한 길로 들어가는 탐색 비교하기
같은 출발점에서 방문 순서를 기록하세요. 모든 간선 비용이 같을 때 BFS에서 처음 도착한 거리는 최소 간선 수가 되지만 DFS의 첫 길은 더 길 수 있습니다.
BFS / DFS 탐색 열기 →목표에 가까워 보이는 후보 살펴보기
지나온 비용과 목표까지 예상 비용을 함께 봅니다. 목적지 바로 앞에 벽이 있으면 눈으로 가깝게 보이는 칸이 실제 최선 경로와 어떻게 다른지 확인하세요.
A* 경로탐색 열기 →비용이 가장 작은 대기 후보 찾기
직행 비용이 8이고 두 구간을 거치면 3과 2인 예를 떠올리세요. 음수가 없는 그래프에서 후보 비용이 더 작아질 때 이전 경로가 어떻게 바뀌는지 보세요.
다익스트라 최단경로 열기 →반복할 때 거리 정보가 퍼지는 방향 보기
음수 간선이 있는 경로에서 완화 이전과 이후의 거리를 비교하세요. 도달 가능한 음수 사이클이 있다면 한 바퀴 더 돌 때마다 비용이 낮아질 수 있습니다.
벨만-포드 열기 →중간 지점을 하나 허용한 거리표 읽기
A에서 C로 바로 가는 비용과 B를 거치는 비용을 비교하세요. 한 중간 지점에 대한 갱신이 끝날 때마다 여러 출발지의 값이 함께 바뀝니다.
플로이드-워셜 열기 →찾은 경로와 살핀 칸 수 구분하기
같은 지형에서 여러 탐색 과정을 나란히 보세요. 같은 길이를 찾아도 방문한 칸의 수와 방문 순서는 다를 수 있습니다.
경로탐색 비교 열기 →경계가 한 칸 끊긴 그림 떠올리기
닫힌 윤곽 안을 채우다가 같은 색의 틈이 열려 있으면 바깥으로도 채우기가 이어집니다. 연결을 상하좌우로 정했을 때 대각선만 닿은 칸이 포함되는지 살펴보세요.
플러드필 열기 →정렬된 목록에서 후보 반씩 지우기
오름차순 2, 4, 7, 10, 16에서 10을 찾는다면 중간 값 7 이하를 제외할 수 있습니다. 정렬되지 않은 목록에서도 같은 판단이 가능한지 반례를 떠올려 보세요.
이진탐색 열기 →