1525번

1525번 - 퍼즐

이 문제는 처음에 배열로 풀었다. 나름 머리쓴다고, 했지만 결국은 메모리 초과로 인한 런타임 오류...

그래서 STL map 을 공부해서 풀었다. 

일단 map 은 정말 사용하기 좋은 template 인거 같다... 정렬도 되고, 배열처럼 사용할 수도 있고... 단 중복은 안되므로 그럴때는 multimap을 이용.

처음에 map을 배워서 map 의 인덱스 값으로 string을 이용했는데, 이 마저도 메모리 초과가 일어났다.

그래서 결국은 string 을 stoi 함수를 통해 모두 int 로 변경에서 index 로 입력했더니 AC를 받을 수 있었다.

결국 이 문제는 3 x 3 크기의 맵을 int 형 변수로 변경하고, 이를 map 을 통해 방문여부 체크하는 용도로 사용하여, bfs를 돌리면 되는 문제였다.

<정답 코드>

#include<iostream>
#include<map>
#include<string>
#include<queue>
using namespace std;
 
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int m[3][3];
string mToString(int tmp[][3])
{
    string ret = "";
 
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            ret += tmp[i][j] + '0';
        }
    }
 
    return ret;
}
string makeNewM(int x,int y,int nx,int ny,string M)
{
    int tmp[3][3];
    int cnt = 0;
 
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            tmp[i][j] = M[cnt++]-'0';
        }
    }
 
    swap(tmp[x][y], tmp[nx][ny]);
 
    string ret = mToString(tmp);
 
    return ret;
}
int main()
{
    int x0, y0;
    string m0;
    int goal = 123456780;
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            cin >> m[i][j];
            if (m[i][j] == 0)
            {
                x0 = i;
                y0 = j;
            }
        }
    }
    m0 = mToString(m);
    map<int, int> distance;
    queue<pair<pair<int,int>,string>> q;
    q.push(make_pair(make_pair(x0, y0), m0));
    distance[stoi(m0)] = 0;
 
    while (!q.empty())
    {
        int x = q.front().first.first;
        int y = q.front().first.second;
        string M = q.front().second;
        q.pop();
 
        if (stoi(M) == goal)
        {
            break;
        }
 
        for (int d = 0; d < 4; d++)
        {
            int nx = x + dx[d];
            int ny = y + dy[d];
 
            if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3)
            {
                string nM = makeNewM(x,y,nx,ny,M);
                if (distance.count(stoi(nM)) == 0)
                {
                    distance[stoi(nM)] = distance[stoi(M)] + 1;
                    q.push(make_pair(make_pair(nx, ny), nM));
                }
            }
        }
 
    }
 
    if (distance.count(goal) == 0)
    {
        cout << "-1" << endl;
    }
    else
    {
        cout << distance[goal] << endl;
    }
    return 0;
}