[BOJ] 1525 퍼즐

 

1525번: 퍼즐

 

 

#include <iostream>
#include <map>
#include <queue>
#define TARGET "123456780"
using namespace std;

string Input;
map<string, bool> visit;
queue<pair<string, int>> q;
int d[4] = { -3, -1, 1, 3 };


void input(){
    int i =0 ;
    string N;
    while( i++ < 9){
        cin >> N;
        Input += N;
    }
}
bool possible(int cur, int d){
    if( (cur % 3) == 0 && d == -1)
        return false;
    if( (cur % 3) == 2 && d == 1)
        return false;

    return ( cur + d < 0 || cur + d > 8 ) ? false : true;
}
int bfs(){
    visit[Input] = true;
    q.push({Input,0});

    while(!q.empty()){
        string cur = q.front().first;
        int cnt = q.front().second;

        q.pop();

        if(cur.compare(TARGET) == 0)
            return cnt;

        int cur_blank = cur.find('0');
        for(int i =0 ; i < 4; i++){

            if(possible(cur_blank, d[i])){
                string cur_next = cur;

                cur_next[cur_blank] = cur[ cur_blank+d[i] ];
                cur_next[ cur_blank+d[i] ] = '0';

                if(!visit[cur_next]){

                    q.push({cur_next, cnt + 1});
                    visit[cur_next] = true;
                }

            }
        }
    }
    return -1;

}
int main() {
    input();
    cout << bfs() <<endl;

    return 0;
}

 

 

1차원으로 생각하고 문제를 풀었는데 그렇게 하면 배열에서 벗어나는 곳을 찾지 못하는 경우가 생겼다. 2차원 배열은 2차원으로 생각하는게 예외 상황을 안만들어낼 것 같다.

 

 

 

 

백준 1525번 퍼즐

글 읽기 - 반례는 찾았는데 왜 잘못된 결과가 나왔는지 이해하지 못하겠습니다.