Computer Science
A* Search : 8-ํผ์ฆ ๋ฌธ์ ๋ก ์์๋ณด๊ธฐ
9/16/2025

8-ํผ์ฆ์ด ๋ญ์์?
8-ํผ์ฆ์ด๋ 3x3 ๊ฒฉ์ํ์์ 1๋ถํฐ 8๊น์ง ์ซ์๊ฐ ์ฐ์ฌ์๋ 8๊ฐ์ ํ์ผ๊ณผ ํ๋์ ๋น์นธ์ ์์ง์ฌ ํ์ผ์ ์์๋๋ก ๋ฐฐ์ดํ๋ ํผ์ฆ์ ๋๋ค. ์ ์ญ์๋ ์ด๋ฆด์ ๋งํ ์บ๋ฆญํฐ๊ฐ ๊ทธ๋ ค์ง 8-ํผ์ฆ์ ํ๊ณค ํ๋๋ฐ, ์ ์๋ ๋๋ง๋ค ์ด๋จธ๋๊ป ๋ถํ๋๋ ธ๋ ๊ธฐ์ต์ด ๋ฉ๋๋ค. ํ๋์ ์๊ณ ์ด๋ค๊ฐ 26์ด์ด ๋๊ณ ๋์์ผ ์ด ํผ์ฆ์ ํด๊ฒฐํ ๋ฐฉ๋ฒ์ ์์๋์ต๋๋ค. (์ฒ์ ๋ค์ด๋ณด์ ๋ค๋ฉด ์๋ ํผ์ฆ์ ์์ง์ฌ ๋ฌธ์ ๋ฅผ ํ ๋ฒ ํ์ด๋ณด์ธ์)
Eight Puzzle
๋น ์นธ๊ณผ ์ธ์ ํ ์ซ์๋ฅผ ํด๋ฆญํด ํผ์ฆ์ ์์ฑํด๋ณด์ธ์.
์ด๋ ํ์: 0
๋ฌธ์ ํด๊ฒฐ์ ๊ณง ํ์
ํผ์ฆ์ ์ด๊ธฐ ์ํ๋ก ์์ํฉ๋๋ค. ์ด๊ธฐ ์ํ์์ ํ ์ ์๋ ํ๋์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
1. UP: ๋น์นธ์ ์๋ก ์ฌ๋ฆฌ๊ธฐ (ํ์ผ์ ์๋๋ก ๋ด๋ฆฌ๊ธฐ)
2. DOWN: ๋น์นธ์ ์๋๋ก ๋ด๋ฆฌ๊ธฐ (ํ์ผ์ ์๋ก ์ฌ๋ฆฌ๊ธฐ)
3. LEFT: ๋น์นธ์ ์ผ์ชฝ์ผ๋ก ์ฎ๊ธฐ๊ธฐ (ํ์ผ์ ์ค๋ฅธ์ชฝ์ผ๋ก ์ฎ๊ธฐ๊ธฐ)
4. RIGHT: ๋น์นธ์ ์ค๋ฅธ์ชฝ์ผ๋ก ์ฎ๊ธฐ๊ธฐ (ํ์ผ์ ์ผ์ชฝ์ผ๋ก ์ฎ๊ธฐ๊ธฐ)
ํ์ผ์ ์ํ์ ๋ฐ๋ผ์ ํน์ ํ๋์ ๋ถ๊ฐ๋ฅํ ์๋ ์์ต๋๋ค. ์ด๋ฏธ ๋น์นธ์ด ๊ฐ์ฅ ์์ ์๋ ๊ฒฝ์ฐ, UP ๋์์ ๋ถ๊ฐํฉ๋๋ค.
๊ฐ ํ๋์ ํ ๋๋ง๋ค ํผ์ฆ์ ์ํ๋ ๋ณํํฉ๋๋ค. ์ฐ๋ฆฌ์ ๋ชฉํ๋ ์ ํ๋๋ค์ ์กฐํฉํ์ฌ ๊ฐ์ฅ ์ ์ ํ์๋ง์ผ๋ก ๋ชฉํ ์ํ(1๋ถํฐ 8๋ฒ ํ์ผ์ด ์ ๋ ฌ๋ ์ํ)์ ๋๋ฌํ๋ ๊ฒ์ ๋๋ค.
๋ชฉํ ์ํ์ ๋๋ฌํ๊ธฐ ์ํด ํผ์ฆ์ ์ฌ๋ฌ ์ํ๋ฅผ ๊ฑฐ์ณ์ผ ํฉ๋๋ค. ์ด ์ํ๋ค์ ์ ์ด๋ฅผ ๊ทธ๋ฆผ์ผ๋ก ํํํด๋ณด๋ฉด ๋ค์๊ณผ ๊ฐ์ ๊ฒ์ ๋๋ค.

๊ฐ ์ํ๋ค์ ๋ค์ ์ํ๋ค์ ๋ณ๊ณ , ์ด๋ ํธ๋ฆฌ ๊ตฌ์กฐ๋ฅผ ๋ณด์ ๋๋ค. ํธ๋ฆฌ๋ค์ ํ์ํ๋ค๋ณด๋ฉด ์ธ์ ๊ฐ๋ ๋ชฉํ ์ํ์ ํด๋นํ๋ ํ์ผ์ด ๋์ฌ ๊ฒ์ด๋ฉฐ, ํธ๋ฆฌ์ ๊น์ด๋ ์ด๋ ํ์๋ฅผ ๋ํ๋ด๋ฏ๋ก BFS๋ฅผ ์ฌ์ฉํ๋ฉด ์ต์ ์์ง์์ผ๋ก ๋ชฉํ ์ํ๋ก ์ด๋ํ๋ ๋ฐฉ๋ฒ์ ์ฐพ์ ์ ์์ต๋๋ค.
BFS์ ํตํ ํด๊ฒฐ
์ค๋ณต ์ฒ๋ฆฌ
BFS๋ก ๊ตฌํ์ ํ ๋์๋ ์ค๋ณต ์ฒ๋ฆฌ๋ฅผ ์ ๊ฒฝ์จ์ฃผ์ด์ผ ํฉ๋๋ค. ๊ฐ์ฅ ๋จผ์ ๋ง๋ ์ ์๋ ์ค๋ณต์ ์ฒซ ํ๋์ ๋ฐ๋ ํ๋์ด ๋ฐ๋ก ์ด๋ฃจ์ด์ง๋ ์ํฉ์ ๋๋ค. UP -> DOWN ํ๋์ด ์ด๋ฃจ์ด์ง๋ฉด ์๋์ ์ํ๋ก ๋์๊ฐ๋๋ค. ๋ฐ๋ ํ๋๋ง ๋ง๋ ๊ฒ์ ์๋ฒฝํ๊ฒ ์ค๋ณต์ ๋ง์ ์ ์๋๋ฐ, ์ด๋ UP -> LEFT -> DOWN -> RIGHT์ ๊ฐ์ ์ฌ์ดํด์ด ๋ฐ์ํ ์ ์๊ธฐ ๋๋ฌธ์ ๋๋ค.
์ด๋ฅผ ๊ฐ๋จํ๊ฒ ํด๊ฒฐํ๊ธฐ ์ํด ๋ฐฐ์ด์ธ ๊ฐ ํผ์ฆ ์ํ๋ฅผ ๋ฌธ์์ด๋ก ์ง๋ ฌํํ๊ณ , ์ํ ๋ฌธ์์ด์ ์งํฉ์ ์ ์ฅํ์ฌ ์ค๋ณต๋ ์ํ๊ฐ ๋ฐ์ํ์ง ์๋๋ก ๋ง๋ค์ด์ฃผ์์ต๋๋ค.
๊ตฌํ
public static class Node {
final int[][] board;
final int moved;
// constructor
}๊ฐ ๋ ธ๋๋ 3x3์ ํผ์ฆ ์ํ์ ๊ธฐ์กด์ ๋ช ํ ์์ง์๋์ง์ ๋ํ ์ ๋ณด๋ฅผ ๊ฐ์ง๊ณ ์์ต๋๋ค. (๊ธฐํ ์ต์ ํ์ ํ์ํ ๋ณ์๋ค์ ๋ค ์จ๊ธฐ๊ณ ํต์ฌ ํ๋๋ง ๋จ๊ฒผ์ต๋๋ค.)
void solve() {
Node initial = new Node(new int[][]{
{8, 6, 7},
{2, 5, 4},
{3, 0, 1}
}, 0);
Queue<Node> q = new LinkedList<>();
Set<String> visited = new HashSet<>();
int nodeVisits = 0;
visited.add(serialize(initial.board));
q.add(initial);
while (!q.isEmpty()) {
Node node = q.poll();
nodeVisits++;
if (isGoal(node.board)) {
System.out.println("Total nodes visited: " + nodeVisits);
System.out.println("Solved in " + node.moved + " moves.");
return;
}
List<Node> nextNodes = expand(node);
for (Node n : nextNodes) {
String serialized = serialize(n.board);
if (!visited.contains(serialized)) {
visited.add(serialized);
q.add(n);
}
}
}
}์ด๊ธฐ ์ํ ๋ ธ๋๋ก ์์ํ์ฌ ์ํ๋ฅผ ์์ํฉ๋๋ค. ๋ ธ๋ ๋ฐฉ๋ฌธ ์ดํ expand() ํจ์๋ฅผ ํตํด ๊ฐ๊ฐ์ ์ก์ ์ด ์ํ๋ ์ดํ ์ํ์ ๋ ธ๋๋ค์ ์์ฑํ๋ฉฐ, ํด๋น ์ํ๊ฐ ์ค๋ณต์ด ์๋ ๊ฒฝ์ฐ ํ์ ์ถ๊ฐ๋ฉ๋๋ค.
์ด๋ฅผ ํตํด 31๋ฒ์ ์ด๋์ผ๋ก ์ฃผ์ด์ง ์ด๊ธฐ ์ํ์ ํผ์ฆ์ ๋ชฉํ ์ํ๋ก ๋ง๋ค ์ ์๋ค๋ ๊ฒ์ ์๊ฒ ๋์์ต๋๋ค. ์ด ๊ณผ์ ์์ ๋ฐฉ๋ฌธํ ๋ ธ๋ ์ ์ญ์ ๊ณ์ฐํ์ฌ ์ถ๋ ฅํด ๋ณด์๊ณ , ๊ฒฐ๊ณผ๋ก๋ 181,439ํ๊ฐ ๋์์ต๋๋ค.
๋ฅํฐ ์คํธ๋ ์ธ์ง๋ ์๊ฐ ์กฐ์ข ๋ฅ๋ ฅ์ด ์์ด ๋ฌด์ํ ๊ฒฝ์ฐ์ ์๋ฅผ ๋ณด๊ณ ๋์๋ ์๋ ์๊ฐ์ผ๋ก ๋์์ฌ ์ ์์ต๋๋ค. ํ์ง๋ง ์ปดํจํฐ๋ ๊ทธ๋ฐ ๋ฅ๋ ฅ์ด ์์ด ๊ฒฝ์ฐ์ ์๋ฅผ ๋ณด๋๋ฐ์ ์๊ฐ์ด ์๋น๋ฉ๋๋ค. ์ง๊ธ์ 3x3 ํผ์ฆ์ด๋ผ ๊ธ๋ฐฉ ๋์ง๋ง, 4x4, 5x5์ ๊ฐ์ด ๋์ด๋๋ค๋ฉด ์ํ ์๊ฐ์ ๊ธฐํ๊ธ์์ ์ผ๋ก ๋์ด๋ ๊ฒ์ ๋๋ค.
A* Search๋ฅผ ํตํ ํด๊ฒฐ
Traditional Search vs Informed Search
BFS๋ ์ ํต์ ์ธ ํ์ ๋ฐฉ์์ผ๋ก์จ, ์ด๋ค ์ ๋ ฅ์ด ๋ค์ด์ค๋ ํญ์ ๊ธฐ๊ณ์ ์ธ ๊ท์น์ ํ ๋๋ก ๋ ธ๋๋ฅผ ํ์ํฉ๋๋ค.
ํ ํธ, ํด๋ฆฌ์คํฑ ํ์Informed Search ๋ฐฉ์์ ๋ฌธ์ ์์ ์ฃผ์ด์ง ์ ๋ณด๋ฅผ ๋ฐํ์ผ๋ก ํ์์ ์งํํฉ๋๋ค. ์ด๋ฅผ ํตํด ์ ํต์ ํ์ ๋ฐฉ์๋ณด๋ค ๋ ํจ์จ์ ์ผ๋ก ์๋ฃจ์ ์ ์ฐพ์ ์๋ ์์ต๋๋ค.
Best-first Search๋ ํด๋ฆฌ์คํฑ ํ์์ ํ ์๋ก, ํ๊ฐ ํจ์ f(n)์ ํ ๋๋ก ๊ฐ๊ฐ์ ์ํ ๊ณต๊ฐ์ด ์ผ๋ง๋ ๋ชฉํ์ ๊ทผ์ ํ ๊ฐ๋ฅ์ฑ์ด ์๋์ง๋ฅผ ์ถ์ ํฉ๋๋ค. ์ด๋ฅผ ํ ๋๋ก ๊ฐ์ฅ ๋ชฉํ์ ๊ทผ์ ํ๋ค๊ณ ์์ธก๋๋ ํธ๋ฆฌ๋ฅผ ์ฐ์ ์ ์ผ๋ก ํ์ํ์ฌ ๋ถํ์ํ ํ์์ ์ค์ผ ์ ์์ต๋๋ค.
A* Algorithm (A* Search)
A* Algorithm ํน์ A* Search๋ผ๊ณ ๋ถ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ Best-first Search ๋ฐฉ์์ ์ฌ์ฉํฉ๋๋ค. ํ๊ฐํจ์๋ฅผ ํตํด ์ํ๋ค์ ๊ฐ๋ฅ์ฑ์ ์์ธกํ๊ณ , ๋ถํ์ํ ๊ฐ์ง๋ ์๋ผ๋ฒ๋ฆผ์ผ๋ก์จ ๋ ์ ์ ๋ ธ๋๋ฅผ ํ์ํ๊ณ ํจ์จ์ ์ผ๋ก ๊ฒฐ๊ณผ๋ฅผ ๋์ถํด๋ ๋๋ค.
A* Search์ ํ๊ฐํจ์ f(n)์ ๋ค์๊ณผ ๊ฐ์ด ๊ตฌ์ฑ๋ฉ๋๋ค: f(n) = g(n) + h(n)
n์ ๊ฐ ์ํ ๋ ธ๋๋ฅผ ์๋ฏธํฉ๋๋ค. g(n)์ ์ด๊ธฐ ๋ ธ๋๋ก๋ถํฐ ๋ ธ๋ n ๊น์ง ๋๋ฌํ๋๋ฐ์ ์ฌ์ฉ๋ ๋น์ฉ์ ์๋ฏธํฉ๋๋ค. h(n)์ ํด๋ฆฌ์คํฑ ํจ์๋ก, ๋ ธ๋ n์์๋ถํฐ ๋ชฉํ ๋ ธ๋๊น์ง ๋๋ฌํ๋๋ฐ์ ํ์ํ ๋น์ฉ์ ์ถ์ ํ ๊ฐ์ ๋๋ค. ๊ฒฐ๊ณผ์ ์ผ๋ก f(n)์, n ๊น์ง ๋๋ฌํ๋๋ฐ์ ๋ ๋น์ฉ๊ณผ ๋ชฉํ ์ํ์ ๋๋ฌํ ๋๊น์ง ๋ค ๋น์ฉ์ ๋ํ ์ถ์ ์น์ ํฉ์ผ๋ก, ํด๋น ๋ ธ๋๊ฐ ์ต์ ํด์ ์ผ๋ง๋ ๊ฐ๊น์ธ์ง ํ๊ฐํ๋ ๊ธฐ์ค์ด ๋ ์ ์์ต๋๋ค.
8-ํผ์ฆ ๋ฌธ์ ์์ ๊ฐ ์ํ ๋ ธ๋์ ๋ํ f(n)์ ์ด๋ป๊ฒ ๊ตฌ์ฑ๋์ด์ผ ํ ๊น์? ํ ๊ฐ์ง ๋ถ๋ช ํ ์ ์ g(n)์ ํด๋น ๋ ธ๋๊น์ง ์ค๊ธฐ๊น์ง์ ์ด๋ ํ์๊ฐ ๋ ๊ฒ์ด๋ผ๋ ์ ์ ๋๋ค. ๊ทธ๋ ๋ค๋ฉด h(n)์์? ์ด๋ป๊ฒ ํ์ฌ ์ํ์์ ๋ชฉํ ์ํ๊น์ง ๊ฐ ๋๊น์ง์ ์ด๋ ํ์๋ฅผ ์ถ์ ํ ์ ์์๊น์?
h1(n) : ๋ถ์ผ์นํ๋ ํ์ผ ๊ฐ์๋ก ์ถ์

์ ํผ์ฆ์ ๋ด ์๋ค. 1๋ถํฐ 6๊น์ง์ ํ์ผ์ ์ ์์น์ ์๊ณ , 7๊ณผ 8๋ง์ด ์๋ชป ๋ฐฐ์น๋์ด ์์ต๋๋ค. RIGHT -> RIGHT ๋ ๋ฒ์ ์์ง์์ด๋ฉด ํผ์ฆ์ ํด๊ฒฐ๋ฉ๋๋ค.
๋ถ์ผ์นํ๋ ํ์ผ์ ๊ฐ์๋ ์์ผ๋ก ๋จ์ ์ต์ ์์ง์ ํ์์ ์ถ์ ์น๋ก ๋์ํ ์๋ ์๋๋ฐ, ์ด๋ 'ํ๋ฆฐ ์นธ์ ๋ง์ถ๋ ค๋ฉด ์ ์ด๋ ์ด ๋งํผ์ ์์ง์ฌ์ผ ํ๋ค'๋ผ๋ ํํ์ ์๋ฏธ๋ก ์ฌ์ฉ๋ ์ ์๊ธฐ ๋๋ฌธ์ ๋๋ค. h(n)์ ํ๋ฆฐ ํ์ผ ๊ฐ์๋ก ์ ์ํ์ฌ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ค๋ฉด ๋ค์๊ณผ ๊ฐ์ด ๊ตฌํํด ๋ณผ ์ ์์ต๋๋ค.
public static class Node {
final int[][] board;
final int moved;
final int misplacedTiles;
final int estimation;
public Node(int[][] board, int moved) {
this.board = board;
this.moved = moved;
this.misplacedTiles = h();
this.estimation = this.moved + this.misplacedTiles;
}
private int h() {
int count = 0;
if (board[0][0] != 1) count++;
if (board[0][2] != 3) count++;
...
if (board[2][1] != 8) count++;
if (board[2][2] != 0) count++;
return count;
}
}๋ ธ๋๊ฐ ์์ฑ๋๋ ์์ ์ ํ๋ฆฐ ํ์ผ ๊ฐ์๊ฐ ๊ณ์ฐ๋๋ฉฐ, ์ด๋ ์ง๊ธ๊น์ง ์ด๋ํ ํ์์ ํฉ์ฐ๋์ด ๋ ธ๋์ ์ถ์ ๊ฒฐ๊ณผ๊ฐ์ด ๋ฉ๋๋ค. estimation ๊ฐ์ด ๋ฎ์ ๋ ธ๋์ผ์๋ก ๋ ์ ์ ํ์๋ก ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์์ ๊ฒ์ด๋ผ ์์ธก๋๋ ๋ ธ๋์ ๋๋ค. ๋ฐ๋ผ์ ์ด๋ค์ ์ฐ์ ์ ์ผ๋ก ํ์ํ ์ ์๋๋ก ์ฐ์ ์์ ํ๋ฅผ ์ฌ์ฉํด์ผํฉ๋๋ค.
PriorityQueue<Node> q = new PriorityQueue<>(Comparator.comparingInt(n -> n.estimation));
//๋๋จธ์ง ์ฝ๋๋ ๋์ผ์ด๋ ๊ฒ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ๊ฒฝ์ฐ ๋ ธ๋ ๋ฐฉ๋ฌธ ํ์๋ 125,226ํ๊ฐ ๋์ด ๊ธฐ์กด 18๋ง ํ์ ๋นํด ์ฝ 25% ์ค์ด๋ค์์์ ํ์ธํ ์ ์์ต๋๋ค. ์ด๋ ๊ณ ์ ๋ ๊ท์น์ ๋ฐ๋ผ ํ์ํ์ง ์๊ณ , ์์ฑ๋๋ ์ํ๋ค์ ๋ํ ๊ธฐ๋๊ฐ์ ๊ธฐ๋ฐ์ผ๋ก ํ์ ์์๋ฅผ ๊ฒฐ์ ํ์ฌ ๋ถํ์ํ ๋ฐฉ๋ฌธ์ ์ค์๊ธฐ ๋๋ฌธ์ ๋๋ค.
h2(n): manhattan distances๋ก ์ถ์
์์ธก ๋น์ฉ์ ์ถ์ ํ๋ ๋ฐฉ๋ฒ์ ๋ ๊ณ ๋ํํ์ฌ Manhattan Distance๋ฅผ ์ฌ์ฉํด๋ณด๋๋ก ํ๊ฒ ์ต๋๋ค. Manhattan Distance๋ ๋ ์ง์ ์ ์ ์ฌ๋๋ฅผ ํ๊ฐํ๋ ๋ฐฉ๋ฒ ์ค ํ๋๋ก, ์ด๋ฅผ ์ฌ์ฉํ๋ค๋ฉด ๋จ์ํ ํ๋ฆฐ ํ์ผ ๊ฐ์๋ฅผ ๋์ด, ํ์ผ์ด ๊ฐ์ผํ ์์น์ ์ผ๋ง๋ ์ฐจ์ด๊ฐ ๋๋์ง๊น์ง ํ๊ฐ์ ํฌํจ๋ฉ๋๋ค.
private int h() {
int dist = 0;
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
int v = board[r][c];
if (v != 0) {
int tr = (v - 1) / 3, tc = (v - 1) % 3;
dist += Math.abs(r - tr) + Math.abs(c - tc);
}
}
}
return dist;
}H1 ์ฝ๋์์ ์ค์ง h()ํจ์๋ง ์์ ๊ฐ์ด ์์ ํด์ฃผ์์ต๋๋ค. ์์ ๊ฐ์ด ํ๊ฐ ํจ์๋ฅผ ๋ณ๊ฒฝํ ์ดํ, ์ค์ง 7,751ํ์ ๋ ธ๋๋ง์ ๋ฐฉ๋ฌธํ์ฌ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ์์ต๋๋ค. ์ด๊ธฐ BFS์ ๋นํ์ฌ ์ฝ 5%์ ํ์๋ง ์งํํ ๊ฒ์ ๋๋ค.
Admissible Heuristics๊ณผ Performance
๋ชฉํ ์ํ์ ๋ค๋ค๋ฅด๊ธฐ ์ํ ์ต์ ์ด๋ ๋น์ฉ์ ์ถ์ ํ๋ ๋ ํจ์๋ฅผ ์์๋ณด์์ต๋๋ค. ์ด ๋ ํจ์๋ค์ ๋ชจ๋ ํ์ฉ์ ํด๋ฆฌ์คํฑAdmissible Heuristics์ด๊ธฐ์ ์ต์ ํด๋ฅผ ์ฐพ๋ ๊ฒ์ ๋ณด์ฅํฉ๋๋ค.
ํ์ฉ์ ํด๋ฆฌ์คํฑ์ 'ํญ์ ์ค์ ๋น์ฉ์ ํํlower bound์ ์ ๊ณตํ๋ ํด๋ฆฌ์คํฑ ํจ์'๋ฅผ ์๋ฏธํฉ๋๋ค. ์ฌ๊ธฐ์ ์ค์ ๋น์ฉ์ด๋ ๋ ธ๋ n์์ ๋ชฉํ ์ํ๊น์ง์ ์ค์ ์ต์ ๋น์ฉ์ ์๋ฏธํฉ๋๋ค. ์ฆ, ํ ์ํ์์ ๋ชฉํ๊น์ง ์ค์ ๋ก 5ํ์ ์์ง์์ ํ์๋ก ํ๋ค๋ฉด, ํด๋ฆฌ์คํฑ ์ถ์ ์น๋ 5ํ๋ฅผ ์ด๊ณผํด์๋ ์๋๋ค๋ ๊ฒ์ ๋๋ค.
๋ง์ฝ h(n)์ด ์ค์ ๋น์ฉ๋ณด๋ค๋ ๋ ํฐ ๊ฐ์ ๋ด๋ฒ๋ฆฐ๋ค๋ฉด, ์ด๋ค ๋ ธ๋๊ฐ ๋ ์ ๋ ดํ ์ ์์์๋ ๋ถ๊ตฌํ๊ณ ํ๊ฐ ํจ์ ๊ฐ์ด ๋ ์ปค์ ธ์ ํ์์ ๋์์์ ๋ฐ๋ ค๋ ์ ์์ต๋๋ค. ๊ฒฐ๊ตญ ๋ ์ข์ ํด๋ฅผ ๋์น๊ณ , A*๋ ๋น์ต์ ํด๋ฅผ ์ ํํ๊ฒ ๋ฉ๋๋ค.
๊ทธ๋ ๋ค๊ณ ํด์ ํด๋ฆฌ์คํฑ ํจ์๋ฅผ ๋ฌด์กฐ๊ฑด ์ง๋์น๊ฒ ๋ณด์์ ์ผ๋ก ์ค์ ํ๋ ๊ฒ์ด ์ข์ ๊ฒ๋ ์๋๋๋ค. ํด๋ฆฌ์คํฑ ๊ฐ์ด ์ค์ ๋น์ฉ๊ณผ ์ฐจ์ด๊ฐ ํฌ๋ฉด, ํ์ ๊ณผ์ ์์ ๋ง์ ๋ถํ์ํ ์ํ๋ค์ ์ดํด๋ณด๊ฒ ๋์ด ์ฑ๋ฅ์ด ์ ํ๋ฉ๋๋ค. ๋ฐ๋๋ก ํด๋ฆฌ์คํฑ ํจ์๊ฐ ๋งค์ฐ ์ ๋ฐํด์ ์ค์ ๋น์ฉ์ ์ ํํ ์์ธกํ ์ ์๋ค๋ฉด, ํ์์ ๋ถํ์ํ ์ฐํ๋ฅผ ์ ํ ํ์ง ์๊ณ ๊ณง๋ฐ๋ก ์ต์ ๊ฒฝ๋ก๋ฅผ ์ฐพ์๋ผ ์ ์์ต๋๋ค.
๊ฒฐ๊ตญ ์ข์ ํด๋ฆฌ์คํฑ ํจ์๋ ํญ์ ์ค์ ๋น์ฉ์ ๋์ง ์์ผ๋ฉด์๋, ๊ฐ๋ฅํ ์ค์ ๋น์ฉ์ ๊ฐ๊น๊ฒ ์์ธกํ๋ ํจ์๋ผ๊ณ ํ ์ ์์ต๋๋ค.