[ 백준 1525 ] 퍼즐 (C++)

백준의 퍼즐(1525) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1. 본인은 이 문제를 풀 때, int형 맵이 아닌 string 형으로 접근해 보았다. 즉, 우리가 구하고자 하는 정답의 문자열은

   "123456780" 이고, 우리가 입력으로 받은 문자열로 부터, swap이 가능한 위치에 있는 숫자들과 swap을 하면서 답을

   찾아내는 방식으로 구현하였다.

2. 본격적인 문제로 돌입하기 전, string으로 접근할 때, 보다 편리하기 접근하기 위해서 사용된 함수 혹은 방법들에 대해서

   알아보자.

   먼저 string에서는 find함수를 사용할 수 있다. find()함수의 return 값은 Index번호이며, int형이다.

   예를 들어서 string Temp = "12345" 라고 생각해보자.

   이때, Temp.find('2')를 하게되면 1이 반환될 것이다. Temp.find('1')은 0이 반환, 이런식으로 인덱스번호가 반환되는

   find()함수를 이용할 것이다.

   " string.find('a') = 문자열에서 'a'가 있는 곳의 Index번호를 반환해주는 함수 "

  

   그렇다면, 여기서 find함수를 왜 설명했는지 알아보자. 뭔가 대충 느낌적으로 봐도 0 의 위치를 찾아내기 위해서 사용한 것

   같긴 하다. 그렇다면 문제를 다시한번 생각해보자.

   문제에 주어진 예제입력을 확인해보자.

   이것인데, 이거를 본인이 말한대로 문자열로 입력을 받는다면 "103425786"이 될 것이다.

   여기서 0의 위치는 1번째 라는 것을 find()함수를 통해서 알아낼 수 있을 것이다.

   그리고 문제에 조건에 따르면, 0을 기준으로 상하좌우로 인접한 숫자들만 0과 자리를 바꿀 수 있다.

   즉 위에 입력에서는 1, 2, 3이 0과 자리를 바꿀 수 있다는 것이다.

   하지만 우리는 string형으로 입력을 받았다. 맵이 아닌 문자열 103425786 에서, 1, 2, 3이랑만 자리를 바꿀 수 있는 방법을

   찾아야 한다.

  

   그 방법이 문자열을 맵처럼 (x,y)의 자리로 표현하는 것이다.

   방법은 어렵지 않다. 우리가 구한 문자열에서의 인덱스 번호 값을

   x축은 한변의 길이만큼 나눈 몫을, y축은 한변의 길이만큼 나는 나머지의 값을 갖는다.

   int Zero = string.find('0') ==> 0의 위치해 있는 인덱스 번호를 Zero라는 변수에 저장.

   int x = Zero / 3         ==> 한변의 길이가 3이므로, x축은 Zero / 3

   int y = Zero % 3         ==> 한변의 길이가 3이므로, y축은 Zero % 3

   실제로 맞는지 확인을 해보자.

  

   이 코드를 실행시킨 결과값을 보면

   이렇게 나오게 된다.

   맵과 비교해보면, 0은 (0,1)의 자리에 위치해있으며, 일치한다는 것을 알 수 있다.

   이렇게 string -> Map에 mapping 시키는 방법을 알았다면 한 단계 더 응용해서 Map에 mapping -> String도 간단하게

   알아보자.

   (x, y)가 있다면 " x * 한변의 길이 + y " 를 하게 되면 string에서의 Index번호가 나오게 될 것이다.

   (0, 1)에 대입해보면 " 0 * 3 + 1 " = 1 이라는 값이 나오게 되고, 이는 string에서 1번째 Index에 위치한 문자라는 것을

   확인할 수 있다.

3. 본격적인 문제를 풀어보려고 했더니 이미 모든 설명을 다해버렸다.

   BFS()에서 Queue에서는 (string, int) 즉, 현재 문자열과 걸린시간을 쌍으로 관리해 주었다.

   위의 설명 처럼, 매 반복할 때 마다, string에서의 0의 위치와, (x,y)값을 구해주었고, 상하좌우로 인접한 칸들과

   바꿔주고, 다시 string형으로 변환해서 넣어주는 식으로 구현하였다.

4. 여기서 문제가 하나 있다. 완전탐색을 할 때에, 이미 탐색을 해본 정점에 대해서는 다시 탐색을 하지 않는 것이 일반적이다.

   본인과 같이 문제를 해결했다면, 이미 탐색한 string에 대해서는 다시 탐색을 하지 않아야 하는 것이다.

   나는 이 부분을 해결하기 위해서 STL <set>을 사용하였다. set에 대해서 설명하자면...

   #include<set>    →  필요한 Header

   set<변수형> Visit  →  Visit배열과 같은 역할을 하는 놈. ( 이 문제에서는 set<string> Visit )

   Visit.insert("a")   →   "a"를 Visit에 삽입

   Visit.find("a")     →   Visit에 있는 값들 중에서 "a"를 찾기. 찾았다면, 해당 원소가 있는 Index값을 반환

                         찾지 못했다면, end()의 값을 반환.

  

보다 구체적인 내용은 코드를 보면 알 수 있다. set을 이용해서, string도 간단하게 해결할 수 있을 것이다.

[ 소스코드 ]

 

#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#include<string>
 
#define endl "\n"
using namespace std;
 
string Start, End;
set<string> Visit;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
void Input()
{
    End = "123456780";
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            int a; cin >> a;
            char Tmp = a + '0';
            Start = Start + Tmp;
        }
    }
}
 
int BFS()
{
    queue<pair<string, int>> Q;
    Q.push(make_pair(Start, 0));
    Visit.insert(Start);
 
    while (Q.empty() == 0)
    {
        string Cur = Q.front().first;
        int Cnt = Q.front().second;
        Q.pop();
 
        if (Cur == End) return Cnt;
        
        int Zero = Cur.find('0');
        int x = Zero / 3;
        int y = Zero % 3;
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < 3 && ny < 3)
            {
                string Next = Cur;
                swap(Next[x * 3 + y], Next[nx * 3 + ny]);
 
                if (Visit.find(Next) == Visit.end())
                {
                    Visit.insert(Next);
                    Q.push(make_pair(Next, Cnt + 1));
                }
            }
        }
    }
    return -1;
}
 
void Solution()
{
    cout << BFS() << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    freopen("Input.txt", "r", stdin);
    
    Solve();
    return 0;
}