[백준/C++] 1525번 퍼즐

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

1525번: 퍼즐

이 문제는 bfs 탐색을 할 때 마다 입력값을 바꿔주게 되면 다음 탐색에 영향이 가므로, 약간의 테크닉이 필요하다.

그것이 바로 string과 set의 사용이다!

​

우선, 문제의 입력값을 string으로 받는다. 그리고 나서 string의 인덱스 값을 이용하여 행렬 좌표로 변환을 진행한다.

변환된 좌표값으로 상하좌우 주변을 탐색하고, 올바른 범위일 때 좌표값을 다시 string의 인덱스 값으로 변환하여 swap함수를 적용시킨다!

​

여타 bfs와 마찬가지로 방문 여부를 체크해줘야 하므로, set을 이용하여 이미 set에 들어있는 값일 경우 패스하고

들어있지 않을 경우에만 set과 queue에 넣어서 탐색을 진행한다. (set을 find했는데 없다면 end()가 리턴되는 점을 이용!)

728x90

#include <bits/stdc++.h>

using namespace std;

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

string s,ans="123456780";
set<string> visited;

int bfs(){
    queue<pair<string,int>> q;
    q.push({s,0});
    visited.insert(s);

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

        if(cur == ans){
            return cnt;
        }

        // 0의 위치를 기준
        // 문자열 -> 행렬 좌표값으로 변환
        int zero = cur.find('0');
        int x = zero/3;
        int y = zero%3;

        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) continue;

            string next = cur;
            // 행렬 좌표값을 문자열 값으로 변환
            swap(next[x*3+y],next[nx*3+ny]);

            if(visited.find(next)==visited.end()){ // end값이 나오는 건 찾지못했다는 뜻
                visited.insert(next);
                q.push({next,cnt+1});
            }
        }
    }
    return -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    for(int i=0; i<3; i++){
        for(int j=0; j<3;j++){
            int tmp;
            cin >> tmp;
            char c = tmp + '0';
            s += c;
        }
    }
    cout << bfs();
}