백준 - 1525번 퍼즐(C++)

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

1525번: 퍼즐

 

퍼즐의 모든 상태를 queue에 넣어서 관리하는 것이 관건인 문제이다.

퍼즐을 2차원 배열이나 벡터로 만들어 관리하면 되는 문제이지만 이렇게 진행할 경우 방문처리를 진행하는 것이 쉽지 않고 무엇보다 이 문제는 메모리를 상당히 조금 주기 때문에 메모리 초과가 날 가능성이 매우높다. 

 

먼저 방문처리는 겨우 3x3배열이기 때문에 9자리라서 문자열을 사용한 map을 사용하였다. (set도 가능하다. set이 더 좋을듯.)

 

그리고 중요한 퍼즐관리인데, 퍼즐을 2차원 벡터로 보관하지말고 방문처리할 때 사용했던 문자열을 그대로 사용하기로 한다. 하지만 문제가 생긴다.

만약 퍼즐의 형태가 아래와 같다면,

120

345

678

 

문자열로 표현하면

120345678

 

이다. 여기서 0은 2,5와 바꿀 수 있는데 문자열을 통해서는 바꿀 수 있는 위치를 찾을 수 없다. 그래서 약간의 수학식이 필요하다. 

N * M 

a b c

d e f

g h i 

 

배열에서

 

a b c d e f g h i

 

문자열로 변경했을 때, 1행 3열에 존재한 f는 몇번째로 올까? 정답은 N * 3 + 3 = 6 

그렇다면, 반대로 6번째 에 존재하는 f는 몇행 몇 열에 존재할까? 정답은 ( 6 / N , 6 % M  )

 

위 공식은 코딩테스트에서 종종 써먹을 수 있으니 그냥 외우자!

 

자 이제 모든 준비가 끝났다. 자! 우리는 문자열로 퍼즐관리를 하면서 각 자리의 좌표를 구할 수 있게되었다. 

그리고 당연히 우리가 필요한 좌표는 각 퍼즐의 0의 위치이다. 

 

그리고 123456780 이라면 지금까지의 카운트를 반환하면 된다. 

 

#include <iostream>
#include <queue>
#include <map>

using namespace std;
int dx[4] = {1,-1,0,0,};
int dy[4] = {0,0,1,-1};
map<string, bool> visited;

int findIdx(int x, int y){
    return x * 3 + y;
}

pair<int, int> findPoint(int idx){
    return {idx  / 3, idx % 3};
}

string str = "";
int bfs(){
    queue<pair<string, int>> q;
    q.push({str, 0});
    
    visited.insert({str, true});
    while(!q.empty()){
        string now = q.front().first;
        int cnt = q.front().second;
        q.pop();
        
        if(now == "123456780") {
            return cnt;
        }
        
        int now_idx = now.find('0');
        pair<int, int> pos = findPoint(now_idx);
        
        for(int i = 0; i < 4; i++){
            int nx = pos.first + dx[i];
            int ny = pos.second + dy[i];
            
            if(nx < 3 && nx > -1 && ny < 3 && ny > -1){
                int next_idx = findIdx(nx, ny);
                
                string next_str = now;
                next_str[now_idx] = now[next_idx];
                next_str[next_idx] = '0';
                
                if(visited.find(next_str) == visited.end()){ // 못찾음
                    visited.insert({next_str, true});    
                    q.push({next_str, cnt + 1});
                }
            }
        }
    }
    
    return -1;
}

int main()
{
    for(int i = 0; i < 3; i++){
        char tmp;

        for(int j = 0; j < 3; j++){
            cin >> tmp;
            str.push_back(tmp);
        }
    }
    
    cout << bfs() << '\n';
    return 0;
}