[1525] 퍼즐

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

1525번: 퍼즐

<문제>

3*3 보드의 숫자의 배치를 하나의 상태, 1회의 이동으로 도달할 수 있는 상태끼리 연결되어 있다고 생각한다.

구현의 편의상 문자열을 사용하여, 루트노드는 입력으로, 탐색 대상을 "123456780"으로 판별이 가능하다.

문자열 내에서, {1, -1, 3, -3}은 서로 연결되어 있다고 생각할 수 있지만,

가로로 이동하는 경우중 (2, 3)과 (5, 6)은 서로 연결되어있지 않으므로 유의해야 한다.

세로로 이동하는 경우는 인덱스가 [0, 9)의 범위안에 존재하는지에 대한 판별을 해준다면 예외사항은 없다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
typedef struct {
    string s;
    int turn;
} state;
queue<state> q;
set<string> st;
string cmp = "123456780";
int dy[4] = {3, -3, 1, -1};
int main(void) {
    string in = "";
    in.resize(9);
    for (int i = 0; i < 9; i++) cin >> in[i];
    q.push({in, 0});
    st.insert(in);
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        int idx = cur.s.find('0');
        if (cur.s == cmp) {
            cout << cur.turn;
            return 0;
        }
        for (int i = 0; i < 4; i++) {
            int nxt = idx + dy[i];
            if (nxt < 0 || nxt >= 9) continue;
            if (idx == 2 && nxt == 3) continue;
            if (idx == 5 && nxt == 6) continue;
            if (idx == 3 && nxt == 2) continue;
            if (idx == 6 && nxt == 5) continue;
            string temp = cur.s;
            swap(temp[idx], temp[nxt]);
            if (st.find(temp) == st.end()) {
                st.insert(temp);
                q.push({temp, cur.turn + 1});
            }
        }
    }
    cout << -1;
    return 0;
}