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

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

2차원 배열을 문자열로 맵핑해서 해결한다.

1 2 3

4 5 6

7 8 0 

위와 같은 2차원 배열이라면 "123456780" 이러한 문자열이 되는 것이다.

0의 인덱스로부터 2차원 배열에서 0의 위치를 알아낼 수 있다.

한번의 시행에서, 빈칸의 위치를 옮길 수 있는 위치를 찾아준 다음에, 이전 시행에서 찾은 경우만큼만 bfs를 진행한다.

#include<iostream>
#include<set>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;
 
const int dzero[4] = { -3, 3, -1, 1 }; //상하좌우
const int dr[4] = { -1,1,0,0 };
const int dc[4] = { 0,0,-1, 1 };
 
int main(void) {
    string str ="", dst = "123456780";
    
    for (int i = 0; i < 9; i++) {
        int input;
        cin >> input;
        str += input + '0';
    }
    
    set<string> vis;
    vis.insert(str);
    
    queue<string> q;
    q.push(str);
    int cnt = 0;
    
    while(!q.empty()) {
        int qSize = q.size(); //이전 시행에 찾았던 0이 이동 가능한 경우만 실행
        for (int i = 0; i <qSize; i++) {
            string cur = q.front(); //현재 문자열
            q.pop();
 
            if (cur == dst) { //목적 문자랑 같으면 종료
                cout << cnt;
                return 0;
            }
            //cnt++;
 
            int zeroPos=0; //0위치 검색
            for (int j = 0; j < cur.length(); j++) {
                if (cur[j] == '0') {
                    zeroPos = j;
                    break;
                }    
            }
            
            //문자열의 0의 위치로부터 2차원 배열에서의 위치를 맵핑
            int zeroR = zeroPos / 3;
            int zeroC = zeroPos % 3;
 
            for (int j = 0; j < 4; j++) { //0이 움직일 수 있는 방향을 찾음
                int nr = zeroR + dr[j];
                int nc = zeroC + dc[j];
                if (nr < 0 || nc < 0 || nr >= 3 || nc >= 3) continue;
                
                string next = cur;
                swap(next[zeroPos], next[zeroPos + dzero[j]]);
 
                if (vis.find(next) == vis.end()){
                    vis.insert(next);
                    q.push(next);
                }
            }
        }
        cnt++; //이전에 찾은 경우들 다 해보고 
    }
    cout << -1;
    return 0;
}
 

참고: http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220438835865