[1525번] 퍼즐

[문제] 3*3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다.

1	2	3
4	5	6
7	8

어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 다음의 예를 보자.

1		3
4	2	5
7	8	6

1	2	3
4		5
7	8	6

1	2	3
4	5
7	8	6

1	2	3
4	5	6
7	8

가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오.

[예제입력]

1 0 3

4 2 5

7 8 6

[예제출력]

3

[풀이를 위한 개념]

http://twoearth.tistory.com/3?category=809135 (숨바꼭질) 문제에서 사용하는 BFS를 참조하시길 바랍니다.

BFS 는 다음과 같은 문제에 사용되는 알고리즘입니다.

1. 최소 상태의 개수가 충분히 작다.

2. 최소비용을 구하는 문제

3. 이동간극(비용)이 1로 동일해야 한다.

위의 조건을 충족하므로 BFS를 사용하여 구하는 것이 수월합니다.

BFS 문제는 최소경로를 구하는 문제이기 때문에 주로 방문한 node를 방문처리 하기 위해 visited[] 배열을 사용합니다.

또한 이전 node에서 다음 노드에 이동하는 비용이 1로 일정하므로 직전까지 이동한 횟수에 1을 더하면서 이동합니다. (dist[next] = dist[now] + 1; 과 같은 형태)

하지만 이번 문제는 퍼즐의 나열된 순서를 맞춰야 합니다. 순서를 맞추기 위해서 모든 조합형태를 따져보고 퍼즐을 1자로 쭉 펴 놨을 때, "1234567890"의 int형과 일치하면 최소이동비용을 return 할 생각입니다.

[그림1] 빈칸을 0으로 처리하면 맨 앞에 0이 위치할 때, 없어질 수 있으므로 9로 바꾼다.

다른 BFS 문제 처럼 visited[]와 dist[] 배열을 사용한다면 숫자가 너무 중구난방이고 어마어마하게 큰 배열이 필요하므로 배열은 사용하기 적절하지 않다는 걸 알 수 있습니다.

그래서 필요한 자료구조가 map 입니다.

map은 key와 value를 가지고 있습니다. list과 다르지 않습니다. 어렵게 생각할 필요없이 list[a] = b; 일 때, a는 key, b는 value라고 할 수 있습니다. map도 list처럼 중복된 key는 가질 수 없지만 중복된 value는 가질 수 있습니다. 즉 고유의 key를 가지고 있죠.

하지만 다른 점은 list는 순차적으로 데이터를 쌓는 반면, map은 원하는 key에 value(값)을 넣을 수 있죠. 

즉, list는 순차적으로 데이터를 쌓기 때문에 key가 순서를 가지고 있고, map의 key는 순서를 가지고 있지 않기 때문에 고유번호가 되는 것입니다.

(사실 key라는 것이 map에서 고유번호로 쓰이기 때문에 key라고 부르는 것이지, list에서는 그냥 list[1], list[2], list[3]... 순차적으로 저장되기 때문에 key라고 부르지 않습니다.)

그래서 이 문제처럼 방문하는 node가 중구난방이고 node 주소가 큰 값이라면 map을 사용하는 것이 유리합니다.

map은

map<key, value> m;

과 같이 선언합니다. 그리고 사용할 때는 list처럼 

map[key] = value;

로 사용할 수 있습니다.

[풀이과정]

[그림 1]의 퍼즐에서 숫자들은 항상 빈칸을 통해 움직일 수 있습니다. 그 말은 빈칸만 움직일 수 있다는 뜻이 됩니다.

빈칸은 4방향으로 움직일 수 있습니다.

퍼즐 모양에서 x 방향으로 움직일 때와 y 방향으로 움직이는 것을 nx와 ny로 표현해보면

nx[] = {0, 0, -1, 1}

ny[] = {1, -1, 0, 0} 로 만들고

nx[0]와 ny[0] 일 때 위쪽, 

nx[1]와 ny[1] 일 때 아래쪽, 

nx[2]와 ny[2] 일 때 왼쪽, 

nx[3]와 ny[3] 일 때 오른쪽으로 이동하는 것으로 표현할 수 있습니다.

[그림 1]처럼 퍼즐을 한 줄로 나열하고 빈칸은 9로 채워넣습니다. 위에서 말했던 것처럼 빈칸, 즉 숫자 9를 찾아 이동시키면서 우리가 원하는 "123456789"의 int형 숫자를 찾으면 됩니다.

숫자 9의 위치가 int형 숫자의 몇번째에 위치했는지 찾아서 저장하고 

x = 9의 위치 / 3; 

y = 9의위치 % 3 

으로 현재 9의 위치(int형 숫자에서의 위치)가 퍼즐에서 어디에 위치했는지 x , y값으로 저장할 수 있습니다.

[정답]

#include<iostream>
#include<queue>
#include<string>
#include<map>
 
using namespace std;
 
 
int dx[] = {0,0,1,-1};        //행축으로 이동
int dy[] = {1,-1,0,0};        //열축으로 이동
 
int main()
{
 
    int start = 0;
    for(int i = 0; i<3;i++)        //퍼즐 숫자 입력받기
    {
        for(int j = 0; j<3;j++)
        {
            int temp;
            cin >> temp;
            if (temp == 0)
            {
                temp = 9;
            }
 
            start = start*10 + temp;    //퍼즐 숫자를 int형 숫자로 저장
        }
    }
    queue<int> q;
    map<int, int> dist;        // 배열 대신 map을 사용한다.
    dist[start] = 0;
    q.push(start);
 
    while(!q.empty())
    {
        int now_num = q.front();
        string now = to_string(now_num);        //now_num는 int형이므로 string형으로 바꾼다 ('9'를 찾기위해)
        q.pop();
 
        int nn = now.find('9');        // 9의 위치
        int x = nn/3;                // 9의 위치의 행값
        int y = nn%3;                // 9의 위치의 열값
 
        for(int k = 0; k<4; k++)    // 4방향으로 이동
        {
            int nx = x+dx[k];
            int ny = y+dy[k];
 
            if (nx >= 0 && nx < 3 && ny >= 0 && ny <3)        //경계를 넘어가지 않았을 때만 유효한 퍼즐이 된다.
            {
                string next = now;
                swap(next[3*x + y], next[3*nx + ny]);        //일자로 펼쳐진 숫자에서 퍼즐의 4방향에 위치한 숫자와 바꾼다 (실제로 이동하는 작업을 수행하는 부분!)
                int num = stoi(next);                        //다시 int형으로 바꾼다.
                if(dist.count(num) == 0)                    //dist.count(a)는 a라는 key값이 있을 때 1을 return 하고, 없을 때 0을 return한다.
                {                                            //즉, 나오지 않았던 퍼즐(방문하지 않았던 node)만 카운트 한다.
                    dist[num] = dist[now_num] + 1;
                    q.push(num);
                }
            }
        }
    }
 
    if(dist.count(123456789) == 0)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << dist[123456789] << endl;
    }
    return 0;
}

Two Earth_)

궁금한건 질문해주시고 틀린부분은 지적해주시면 감사하겠습니다