[BOJ] 1525 퍼즐

1. 문제 링크

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

2. 문제 해설

이 문제는 얼핏 봐서는 간단한 BFS문제로 보인다. 하지만 실제로 단순한 BFS짜려면 문제가 하나씩 생긴다.

첫번째 문제는 일반적인 BFS와 다르게 움직일 때마다 필요한 상태가 전부 다르기 때문에 큐에 넣을 때 마다 상태를 같이 넣어주어야 한다.

두번째 문제는 첫 번째 문제에서 생기는데, 그냥 상태를 전부 큐에 푸쉬 해서 문제를 내면 메모리 초과가 나온다. 왜냐하면 주어지는 메모리가 16MB밖에 주어지지 않기 때문이다. 평소에는 거의 128MB, 256MB를 잡아서 메모리를 넉넉하게 사용하였지만, 이번 문제는 그렇지 않다. 최대한 메모리를 적게 먹는 방법을 사용해서 풀어야한다.

우리는 총 가지수가 9! 개수 만큼 있다는 것을 알고 있다. 9! 은 계산 해보면 362,880 라는 것을 알 수 있다. 이것을 알고 있다면 가능한 상태를 저장하고, 중복되지 않게 넣어준다면 충분히 16MB 안에 모든 가지수를 넣을 수 있을 것이다. 중복확인은 set을 통해서 logN 만에 확인 가능할 것이다.

1. 우리는 상태를 int형으로 표현할 것이다. 가장 왼쪽 위에서 오른쪽 아래로 순서대로 10억대, 1억대, 이렇게 int로 표현하면 처음 수는 123456780 이라는 수가 초기 상태가 될 것이다.

2. 시작점을 찾아서 BFS를 돌면서 가능한지 set.count를 이용해 logN 만에 중복 확인을 하고, 중복이 아니라면 다음 vector에 집어넣는다.

3. 그렇게 BFS를 하다가 우리가 원하는 상태가 나온다면 경로의 수를 출력 해준다.

이 풀이의 시간복잡도는 모두 상수이므로 O(1)이다. 자세하게 보자면 최악의 경우 모두 보는 가지수 9! 일 것이고(물론 가능한 가지수만 보기 때문에 더 줄어든다. 아마 9! / 2 정도가 될텐데, 그냥 퉁쳐서 9!으로 생각하자.), 중복확인을 하는데에 log(9!)이 필요할 것이므로 9! * log(9!) 이 될 수 있겠다.

3. 소스 코드

#include<iostream>
#include<set>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

struct point{
    char x, y;
    char arr[3][3]={0};
};

bool isSameArr(char a[][3], char b[][3]);
int arr2int(char arr[][3]);

char ans[3][3] = {'1', '2', '3', '4', '5', '6', '7', '8', '0'};

int main(){
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};
    char arr[3][3]={0};
    point temp = {2, 2};
    memcpy(temp.arr, ans, sizeof(ans));
    set<int> s;
    queue<point> q;
    
    //initialize
    s.insert(123456780);
    q.push(temp);
    for (int i=0; i<3; i++) {
        for (int j=0; j<3; j++) {
            scanf(" %c", &arr[i][j]);
        }
    }
    
    if (isSameArr(arr, ans)) {
        printf("0\n");
        return 0;
    }
    
    //BFS
    int cnt=0;
    while (!q.empty()) {
        cnt++;
        int size = (int)q.size();
        for (int l=0; l<size; l++) {
            point cur = q.front(); q.pop();
            for (int i=0; i<4; i++) {
                int check = 0;
                point next = cur;
                next.x += dx[i]; next.y += dy[i];
                if(0 <= next.x && next.x < 3 && 0 <= next.y && next.y < 3){
                    swap(cur.arr[next.y][next.x], cur.arr[cur.y][cur.x]);
                    
                    if (isSameArr(cur.arr, arr)) {
                        printf("%d\n", cnt);
                        return 0;
                    }
                    
                    check = arr2int(cur.arr);
                    if (!s.count(check)) {
                        s.insert(check);
                        memcpy(next.arr, cur.arr, sizeof(cur.arr));
                        q.push(next);
                    }
                    
                    swap(cur.arr[next.y][next.x], cur.arr[cur.y][cur.x]);
                }
            }
        }
    }
    
    printf("-1\n");
    
    return 0;
}

int arr2int(char arr[][3]){
    int hash=0;
    int digit = 100000000;
    for (int i=0; i<3; i++) {
        for (int j=0; j<3; j++) {
            hash += digit * (arr[i][j] - '0');
            digit /= 10;
        }
    }
    return hash;
}

bool isSameArr(char a[][3], char b[][3]){
    for (int i=0; i<3; i++) {
        for (int j=0; j<3; j++) {
            if (a[i][j] != b[i][j]) {
                return false;
            }
        }
    }
    return true;
}

4. 추가 언급

아래 코드를 보면 while문으로 BFS를 돌기 전에 먼저 주어진 배열이 정답인지 아닌지 확인을 한다. 왜 그럴까?

if (isSame(arr, ans)) {
      printf("0\n");
      return 0;
}

우리는 정답인지 아닌지 그 다음 상태를 보면서 확인을 하게 된다. 그 이야기는 모든 상태를 확인하지만, 단 하나. 처음 큐에 들어가 있는 상태는 BFS로는 확인을 하지 못한다. 그렇기에 처음에 먼저 확인을 하고, 정답이 아니라면 BFS를 도는 것이다.

이 문제는 여러 BFS문제에서 일어나는데, 우리는 BFS를 확인할 때 큐에서 빠져나올 때가 아니라 큐에 push 할 때 확인을 해주기에 이러한 문제들이 발생한다. 왜 큐에 push 할 때 확인 하는 지는 http://compasstree934.tistory.com/4 추가 언급에 자세히 적어 놓았으니 더 알고 싶은 사람은 확인을 하면 좋겠다.