백준 11112번 (C++)

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

 

1525번이랑 비슷한 문제다. 다른 점이 있다면 1525번은 입력이 한 번만 들어오는 반면에

 

11112번은 입력이 100개까지 들어올 수 있다는 점이다.

 

그래서 1525번 풀듯이 매 입력마다 최단거리를 구하면 당연히 시간초과가 난다.

 

해결 방법은 123 456 78# 에서 시작해서 모든 상태의 거리를 미리 구해놓고(전처리) 

 

한 상태를 입력 받으면 바로 정답을 출력하는 것이다.

 

모든 경우의 수 9! 에 나올 수 없는 경우(inversion)을 제거하면 9! / 2 = 181,440 번만큼만 탐색하면 된다.

 

 

코드 : 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <deque>
#include <math.h>
#include <memory.h>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <tuple>
#include <numeric>
#define X first
#define Y second
#define INF 0x3f3f3f3f
#define LINF 9223372036854775807
#define MOD 1000000007
#define ll long long
#define int long long
#define pi pair<int, int>
#define ti tuple<int, int, int>
#define T pair<int, pair<string, int>>
using namespace std;
map<string, int> M;
set<string> S;
void copy(string& s, int x1, int x2)
{
    char tmp_x = s[x1];
    s[x1] = s[x2];
    s[x2] = tmp_x;
}
int check(string v)
{
    int flag = 0;
    flag = S.count(v) ? 1 : 0;
    if(!flag)
        S.insert(v);
    return flag;
}
void bfs()
{
    string num = "12345678#";
    queue<T> Q;
    Q.push({ 0,{ num,8 } });
    S.insert(num);
    M[num] = 0;
    while (!Q.empty())
    {
        auto cur = Q.front();
        Q.pop();
        int x = cur.Y.Y;
        if (x % 3 == 0)
        {
            int x1 = x - 3, x2 = x + 1, x3 = x + 3;
            if (x1 > -1)
            {
                string tmp_ = cur.Y.X;
                copy(tmp_, x, x1);
                if (!check(tmp_) || M[tmp_] > cur.X + 1)
                {
                    Q.push({ cur.X + 1,{tmp_,x1}, });
                    M[tmp_] = cur.X + 1;
                }
            }
            if (x2 < 9)
            {
                string tmp_ = cur.Y.X;
                copy(tmp_, x, x2);
                if (!check(tmp_) || M[tmp_] > cur.X + 1)
                {
                    Q.push({ cur.X + 1,{tmp_,x2}, });
                    M[tmp_] = cur.X + 1;
                }
            }
            if (x3 < 9)
            {
                string tmp_ = cur.Y.X;
                copy(tmp_, x, x3);
                if (!check(tmp_) || M[tmp_] > cur.X + 1)
                {
                    Q.push({ cur.X + 1,{tmp_,x3}, });
                    M[tmp_] = cur.X + 1;
                }
            }
        }
        else if (x % 3 == 1)
        {
            int x1 = x - 3, x2 = x - 1, x3 = x + 1, x4 = x + 3;
            if (x1 > -1)
            {
                string tmp_ = cur.Y.X;
                copy(tmp_, x, x1);
                if (!check(tmp_) || M[tmp_] > cur.X + 1)
                {
                    Q.push({ cur.X + 1,{tmp_,x1}, });
                    M[tmp_] = cur.X + 1;
                }
            }
            if (x2 > -1)
            {
                string tmp_ = cur.Y.X;
                copy(tmp_, x, x2);
                if (!check(tmp_) || M[tmp_] > cur.X + 1)
                {
                    Q.push({ cur.X + 1,{tmp_,x2}, });
                    M[tmp_] = cur.X + 1;
                }
            }
            if (x3 < 9)
            {
                string tmp_ = cur.Y.X;
                copy(tmp_, x, x3);
                if (!check(tmp_) || M[tmp_] > cur.X + 1)
                {
                    Q.push({ cur.X + 1,{tmp_,x3}, });
                    M[tmp_] = cur.X + 1;
                }
            }
            if (x4 < 9)
            {
                string tmp_ = cur.Y.X;
                copy(tmp_, x, x4);
                if (!check(tmp_) || M[tmp_] > cur.X + 1)
                {
                    Q.push({ cur.X + 1,{tmp_,x4}, });
                    M[tmp_] = cur.X + 1;
                }
            }
        }
        else if (x % 3 == 2)
        {
            int x1 = x - 3, x2 = x - 1, x3 = x + 3;
            if (x1 > -1)
            {
                string tmp_ = cur.Y.X;
                copy(tmp_, x, x1);
                if (!check(tmp_) || M[tmp_] > cur.X + 1)
                {
                    Q.push({ cur.X + 1,{tmp_,x1}, });
                    M[tmp_] = cur.X + 1;
                }
            }
            if (x2 > -1)
            {
                string tmp_ = cur.Y.X;
                copy(tmp_, x, x2);
                if (!check(tmp_) || M[tmp_] > cur.X + 1)
                {
                    Q.push({ cur.X + 1,{tmp_,x2}, });
                    M[tmp_] = cur.X + 1;
                }
            }
            if (x3 < 9)
            {
                string tmp_ = cur.Y.X;
                copy(tmp_, x, x3);
                if (!check(tmp_) || M[tmp_] > cur.X + 1)
                {
                    Q.push({ cur.X + 1,{tmp_,x3}, });
                    M[tmp_] = cur.X + 1;
                }
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    bfs();
    int t;
    cin >> t;
    while (t--)
    {
        string tmp;
        for (int i = 0; i < 9; i++)
        {
            char x;
            cin >> x;
            tmp.push_back(x);
        }
        if (S.count(tmp))
            cout << M[tmp] << '\n';
        else
            cout << "impossible\n";
    }
}