[백준/BOJ] 1525번 퍼즐 (C++)

www.acmicpc.net/problem/1525

1525번: 퍼즐

독특한 유형의 BFS 문제였습니다. (다시 풀기)

메모리 제한이 있기 때문에 3x3 2차원 배열에 입력값을 저장하지 않고 문자열을 이용해서 1차원으로 입력값을 저장하는 것이 포인트입니다. 예를들어

 

1 0 3

4 2 5          ->      1 0 3 4 2 5 6 7 8 6

7 8 6

 

위에처럼 2차원 배열을 1차원으로 저장하는 것입니다. 이러한 1차원 문자열과 걸린 시간을 큐에 집어 넣으면서 문자열 처리를 해주면 되는데, 이때 0의 인덱스가 어디 있는지 찾는 것이 중요합니다. 이 인덱스를 통해 3x3 배열에서의 0의 x좌표, y좌표를 얻어내어, 이를 이동했을 때 1차원에서의 인덱스 위치를 얻어낼 수 있습니다. 방문을 체크하는 visit은 set을 이용하였습니다.

 

#include <iostream>
#include <queue>
#include <set>
using namespace std;

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

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    // 3x3 배열에 입력값을 저장하지 않고 문자열을 이용해 1차원으로 저장
    string start, target = "123456780";
    for(int i = 0; i < 9; i++) {
        int x;
        cin>>x;
        start.push_back('0' + x);
    }
    
    queue<pair<string, int> > q; // 현재 문자열, 걸린 시간
    set<string> visit; // 문자열이 만들어진건지 체크
    
    q.push({start, 0});
    visit.insert(start);
    
    while(!q.empty()) {
        string now = q.front().first;
        int time = q.front().second;
        q.pop();
        
        if(now == target) {
            cout<<time;
            return 0;
        }
        
        int zero = now.find('0'); // 0이 있는 인덱스 위치
        int x = zero / 3; // 3x3에서의 0의 행 좌표
        int y = zero % 3; // 3x3에서의 0의 열 좌표
        
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
                string next = now;
                swap(next[x * 3 + y], next[nx * 3 + ny]);
                if(visit.find(next) == visit.end()) {
                    q.push({next, time + 1});
                    visit.insert(next);
                }
            }
        }
    }
    cout<<"-1";
}