BAEKJOON
-
[백준-11112] Eight Puzzle (Astar Algorithm)Baekjoon 2020. 5. 12. 14:32
문제 요약 8-Puzzle 게임을 푸는 문제이다. 3x3 보드판에 한칸의 빈공간, 나머지 칸에는 1~8 숫자가 무작위로 위치해 있다. 빈칸과 숫자의 자리를 바꿔 이동시키며 정답을 찾아가는 게임이다. 입력으로 주어지는 보드는 1부터 8사이의 숫자가 섞여있으며 #은 빈 공간을 나타낸다. 빈공간과 인접한 칸의 숫자와 자리를 바꿔보며 원하는 보드의 모양을 만들기 위한 최소의 이동 횟수를 구하면 된다. 문제 풀이 기본적으로 탐색 알고리즘을 통해 풀 수 있는 문제이다. 이 문제에서 제한된 시간은 1초이며 테스트케이스는 100개이다. 제한된 시간 내에 효율적인 탐색 방법으로 풀어야 하는 문제이며 본문에서는 Astar Algorithm을 활용한 풀이를 기술한다. Astar Algorithm은 미래에 가망 있는 값 ..