본문으로 건너뛰기
툴허브

미로와 도로 지도에서 경로 찾기가 달라지는 이유

몇 칸인지, 요금이 얼마인지, 모든 지점 사이의 거리가 필요한지에 따라 문제가 달라집니다. 방문한 칸과 최종 경로를 서로 다른 정보로 읽으세요.

툴허브 편집 ·

층별 탐색과 한 길로 들어가는 탐색 비교하기

같은 출발점에서 방문 순서를 기록하세요. 모든 간선 비용이 같을 때 BFS에서 처음 도착한 거리는 최소 간선 수가 되지만 DFS의 첫 길은 더 길 수 있습니다.

BFS / DFS 탐색 열기 →

목표에 가까워 보이는 후보 살펴보기

지나온 비용과 목표까지 예상 비용을 함께 봅니다. 목적지 바로 앞에 벽이 있으면 눈으로 가깝게 보이는 칸이 실제 최선 경로와 어떻게 다른지 확인하세요.

A* 경로탐색 열기 →

비용이 가장 작은 대기 후보 찾기

직행 비용이 8이고 두 구간을 거치면 3과 2인 예를 떠올리세요. 음수가 없는 그래프에서 후보 비용이 더 작아질 때 이전 경로가 어떻게 바뀌는지 보세요.

다익스트라 최단경로 열기 →

반복할 때 거리 정보가 퍼지는 방향 보기

음수 간선이 있는 경로에서 완화 이전과 이후의 거리를 비교하세요. 도달 가능한 음수 사이클이 있다면 한 바퀴 더 돌 때마다 비용이 낮아질 수 있습니다.

벨만-포드 열기 →

중간 지점을 하나 허용한 거리표 읽기

A에서 C로 바로 가는 비용과 B를 거치는 비용을 비교하세요. 한 중간 지점에 대한 갱신이 끝날 때마다 여러 출발지의 값이 함께 바뀝니다.

플로이드-워셜 열기 →

찾은 경로와 살핀 칸 수 구분하기

같은 지형에서 여러 탐색 과정을 나란히 보세요. 같은 길이를 찾아도 방문한 칸의 수와 방문 순서는 다를 수 있습니다.

경로탐색 비교 열기 →

경계가 한 칸 끊긴 그림 떠올리기

닫힌 윤곽 안을 채우다가 같은 색의 틈이 열려 있으면 바깥으로도 채우기가 이어집니다. 연결을 상하좌우로 정했을 때 대각선만 닿은 칸이 포함되는지 살펴보세요.

플러드필 열기 →