BOJ 1525 퍼즐

BOJ 백준 1525 C++
퍼즐
https://www.acmicpc.net/problem/1525

처음에 이 문제를 봤을 때

접근 시도 첫 번째, 재귀(DFS)가 생각났다. 재귀를 이용하려 해결하려 했지만 재귀 깊이가 어느 정도 가능할지? & 방문 확인을 어떻게 할 것인지? 에 관해 의문이 들었다. 그래도 한번 구현해봤다. 결과는 틀렸습니다.

간단한 경우의 입력에서는 원하는 출력이 나왔지만 아마 예외 케이스에 모두 걸렸을 거로 생각한다. (31을 출력해야 하는 예제에서 -1을 출력한다.)

 

접근 시도 두 번째, 우선 맵으로 주어진다. 그리고 '최소 이동 횟수'를 원한다. = BFS를 이용할 수 있지 않을까? 라는 생각이 강하게 든다.

그런데 지금까지 접해왔던 BFS와는 약간 다르다. 물론 방문했는지 확인하고, 큐를 이용하는 것은 맞지만.

방문했는지 확인할 때, string의 map이나 set을 사용해야 한다. 평소에 사용하지 않던 방법이긴 하다. 그래서 solved 레벨이 gold2인가 싶다.

 

• point 1) 나 역시 처음에는, 평소 해왔던 것처럼 큐에 좌표 위치(x, y)를 넣으려고 했다. -> 값이 "1234567890"인 상태를 찾아야 하므로 좌표 위치가 아니라 맵의 현재 상태와 그에 따른 이동 횟수를 묶어서 푸시했다.
• point 2) 평소에는 방문했던 위치인지 확인하기 위해 check[][] 배열 사용 -> 2차원 맵의 숫자가 지속해서 바뀌기 때문에 2차원 배열에 방문 표시하는 것으로 중복을 체크할 수 없기에 맵의 상태를 string으로 만들어 중복체크 해야한다. set을 사용했다.
• point 3) 원소의 위치를 서로 교환할 때 원래 맵을 수정하면 안 된다. 다른 원소를 확인할 때도 영향이 미친다. 이를 위해 a,b에 저장한 후 서로인 것이 확인될 때 a->b의 값을, b->a의 값을 넣도록 구현했다.

 

• 아쉬운 점 1 : point 3에서 if - else if - else로 중첩되었음 -> 더 깔끔하게 구현 할 수 있지 않을까?
• 아쉬운 점 2 : string num <-> int map[][] 변환을 계속해서 복잡하다는 점(내가 편하게 구현 잘 할 수 있는 방법) -> %3과 /3을 이용해 간단히 구현 할 수 있는 방법이! (익숙하지 않은 방법)

set + string을 자주 사용하지 않는 터라 구현 시 다른 방법이 없을까 계속 생각해봤는데, 중복 체크를 원활히 하기 위해서는 결국 string을 사용해야 할 것 같다는 결론을 내렸다.

 

 

#include <iostream>
#include <queue>
#include <set>
#define N 3
using namespace std;

int map[4][4];
int dx[4] = {0,-1,0,1};
int dy[4] = {-1,0,1,0};

set <string> check;
struct info{
    string str;
    int cnt;
};

int bfs(){
    queue <info> q;

    string num="";
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            num += to_string(map[i][j]);

    q.push({num, 0}); // point 1)
    check.insert(num); // point 2)

    while(!q.empty()){
        string str = q.front().str;
        int cnt = q.front().cnt;
        q.pop();

        if(str=="123456780") return cnt;

        int n = 0;
        int x = 0, y = 0;
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                map[i][j] = str[n++]-'0';

                if(map[i][j]==0){
                    x = i; y = j;
                }
            }
        }

        for(int k=0; k<4; k++){
            int nx = x + dx[k];
            int ny = y + dy[k];
            
            if(0<=nx && nx<N && 0<=ny && ny<N){
                // point 3) swap
                int a = map[nx][ny];
                int b = map[x][y];
                
                num="";
                for(int i=0; i<N; i++){
                    for(int j=0; j<N; j++){
                        if(map[i][j]==a) num += to_string(b);
                        else if(map[i][j]==b) num += to_string(a);
                        else num += to_string(map[i][j]);
                    }
                }

                if(check.find(num)==check.end()){
                    q.push({num, cnt+1});
                    check.insert(num);
                }
            }
        }
    }

    return -1;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            cin >> map[i][j];

    cout << bfs();
    return 0;
}