BOJ

BOJ::1525 퍼즐

BOJ Gold 3

BOJ::1525 퍼즐

Level : Gold 3

시사점

비트마스킹을 시도해서 간략화 해보려 하였지만, 쉽지 않은 문제 입니다.
참고 코드들을 통해 좋은 점들을 배우면 다른 문제에서도 사용이 가능한 테크닉을 배울 수 있을 것 같습니다.

이해(x)

어릴때 한번씩은 해봤을만한, 8개의 퍼즐 9개의 공간을 정해진 위치로 정렬하는 문제입니다.

설계(x)

시간 복잡도

공간 복잡도

구현(x)

디버깅(x)

좋은 코드

djm03178 님의 백준 공개 코드를 가져왔습니다.
비트마스킹, 9진법처리, 메모리 아끼기 등 배울 게 많다고 생각합니다.
완벽한 이해가 되는대로, 주석을 추가해 이해를 돕겠습니다.

#include <cstdio>
#include <cstring>
#include <utility>
using namespace std;

int x[3][3] = { 1, 2, 3, 4, 5, 6, 7, 8 };
unsigned char v[5381000];
int mul[9];

void bitmask(int &n)
{
    int i, j;
    n = 0;
    for (i = 0; i < 3; i++)
        for (j = 0; j < 3; j++)
            n += mul[x[i][j]] * (i * 3 + j);
}

void fetch(int a, int b)
{
    int n = a * 8 + b;
    int i;
    memset(x, 0, sizeof(x));
    for (i = 8; i >= 1; i--)
    {
        int k = n / mul[i];
        x[k / 3][k % 3] = i;
        n %= mul[i];
    }
}

const int MAX = 2300000;
int q[MAX];
int ft, bk;

int main()
{
    int i, j;
    int a, b, xa, xb, n;
    for (i = 1, j = 1; i <= 8; i++, j *= 9)
        mul[i] = j;
    bitmask(n);
    xa = n / 8;
    xb = n % 8;
    for (i = 0; i < 3; i++)
        for (j = 0; j < 3; j++)
            scanf("%d", &x[i][j]);
    if (getchar() != '\n') while (1);
    bitmask(n);
    a = n / 8;
    b = n % 8;
    v[a] |= (1 << b);

    q[bk++] = n;

    int dx[] = { 0, 0, 1, -1 };
    int dy[] = { 1, -1, 0, 0 };
    int t = 0;
    while (ft != bk)
    {
        for (int cnt = bk; ft != cnt;)
        {
            int cur = q[(ft++) % MAX];
            a = cur / 8;
            b = cur % 8;

            if (a == xa && b == xb)
            {
                printf("%d", t);
                return 0;
            }

            fetch(a, b);
            for (i = 0; i < 3; i++)
                for (j = 0; j < 3; j++)
                    if (x[i][j] == 0)
                        goto okay;
        okay:
            for (int k = 0; k < 4; k++)
            {
                int ny = i + dy[k];
                int nx = j + dx[k];
                if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3)
                {
                    swap(x[ny][nx], x[i][j]);
                    bitmask(n);
                    a = n / 8;
                    b = n % 8;
                    if (!(v[a] & (1 << b)))
                    {
                        v[a] |= (1 << b);
                        q[(bk++) % MAX] = n;
                    }
                    swap(x[ny][nx], x[i][j]);
                }
            }
        }
        t++;
    }
    printf("-1");
}