1525번 퍼즐

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

 

문자열 처리 + bfs

 

방문처리는 문자열로 처리해준다. 문자열에 대한 방문처리는 set이 좋다.

 

 

#include <bits/stdc++.h>

using namespace std;

string s = "", goal = "123456780";
int dy[4] = { 1, 0, -1, 0 };
int dx[4] = { 0, 1, 0, -1 };
set<string> st;

int bfs()
{
    queue<string> q;
    q.push(s);
    st.insert(s);

    int ret = 0;

    while (!q.empty())
    {
        int qs = q.size();

        while (qs--)
        {
            string now = q.front();

            q.pop();

            if (now == goal) {
                return ret;
            }

            int idx = now.find('0');
            int r = idx / 3, c = idx % 3;

            for (int i = 0; i < 4; i++) {
                int y = r + dy[i];
                int x = c + dx[i];

                if (y < 0 || y >= 3 || x < 0 || x >= 3) {
                    continue;
                }

                int next_idx = 3 * y + x;
                string next = now;
                swap(next[idx], next[next_idx]);

                if (st.count(next) == 0) {
                    st.insert(next);
                    q.push(next);
                }

            }
        }

        ++ret;
    }

    return -1;
}

int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\lazy_bronze\\2.in", "r", stdin);
    cin.tie(0);

    int n;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            scanf("%d", &n);
            s += to_string(n);
        }
    }

    int ans = bfs();

    if (ans == -1) printf("-1\n");
    else printf("%d\n", ans);

    return 0;
}