#1525 퍼즐

우리는 4x4짜리 슬라이딩 퍼즐은 자주 갈지고 놀게 됩니다.

 

슬라이딩 퍼즐은 아래의 그림과 같이 생겼는데요.  비어있는 칸이 있고, 이 칸의 주변 상하좌우에서 숫자를 옮길 수 있습니다.

 

슬라이딩 퍼즐

이번 문제는 4x4 슬라이딩 퍼즐이 아니고 3x3 슬라이딩 퍼즐입니다.

슬라이딩 퍼즐이 주어지면, 가장 빠르게 맞출 때 최소의 이동횟수를 푸는 것입니다.

불가능한 경우도 생깁니다.  이건 숫자가 있어야할 곳과 비어있는 칸의 위치로 원래 판단할 수 있습니다.  하지만, 그것을 이용해서 프로그램하지는 않았습니다.

 

https://www.acmicpc.net/problem/1525

1525번: 퍼즐

 

저는 너비 우선 탐색(BFS)를 이용하여 문제를 풀었습니다.  왜 다익스트라나 A* 알고리즘을 쓰지 않았는가 궁금할 수 있겠죠.  일단 이동 경로의 간선의 가중치가 모두 1이면 다익스트라 알고리즘이나 너비 우선 탐색 알고리즘은 동일합니다.  A* 알고리즘을 적용하면 더 빠르게 문제를 풀 수는 있습니다.  하지만 모든 경우의 수를 따져보면 그다지 효율적이지 않고, 예측 경로의 이동수가 실제 움직여야 하는 거리보다 훨씬 짧게 구성해야 하므로 결국 탐색해야 하는 경우의 수가 많아집니다.  A* 알고리즘은 예측 경로가 실제와 비슷할 수록 효율적이니까요.

 

일단 퍼즐의 빈칸을 0으로 나머지는 숫자로 표현해서 그래프 노드를 표현했습니다.

1		3
4	2	5
7	8	6

위와 같은 경우에는 103425786 으로 표현했습니다.  최대 자릿수는 9자리수이므로 정수형 변수로 표현할 수 있습니다.

대신 방문했음을 표시해주기 위해서는 해시맵을 이용했습니다.  메모리 공간을 할당하기에는 너무 많으니까요.

 

그래서 작성한 소스입니다.  소스는 참고용으로만 봐주세요.

//-----------------------------------------------------------------------------------
//    baekjoon #1525 - Puzzle
//        - by Aubrey Choi
//        - created at 2019-11-27
//-----------------------------------------------------------------------------------
#include <stdio.h>
#include <unordered_map>
#include <queue>

int main()
{
    int goal=123456780, s=0, t, i, j, r, c, rc, nr, nc, nrc, ns, v[100];
    const int d[][2]={0,1, 1,0, 0,-1, -1,0};
    std::unordered_map<int,int> map;
    std::queue<int> q;
    for(i=0;i<9;i++) { scanf("%d",&t); s=s*10+t; }
    q.push(s); map[s]=0;
    while(!q.empty())
    {
        s=q.front(); q.pop();
        for(i=0,t=100000000;i<9;i++,t/=10) v[i]=(s/t)%10;
        if(s==goal) break;
        for(rc=0;rc<9;rc++) if(!v[rc]) break;
        r=rc/3, c=rc%3;
        for(i=0;i<4;i++)
        {
            nr=r+d[i][0], nc=c+d[i][1], nrc=nr*3+nc;
            if(nr<0||nr>=3||nc<0||nc>=3) continue;
            for(ns=0,j=0;j<9;j++) ns=ns*10+((j==rc)?v[nrc]:(j==nrc)?0:v[j]);
            if(map.find(ns)!=map.end()) continue;
            q.push(ns); map[ns]=map[s]+1;
        }
    }
    printf("%d\n", s==goal?map[s]:-1);
}