[백준 1525] 퍼즐, C++

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

1525번: 퍼즐

본 문제는 지금까지 풀었던 BFS와 저장과 확인 방식의 차이가 있어 글을 쓰게 되었다. 그 동안 BFS는 2차원 배열로 정보를 저장하여 최단 거리를 구했는데 이 문제는 string과 set을 이용하여 최단 거리를 구하였다. 실제 코딩 테스트나 시험에 나왔으면 많이 당황할 문제라고 생각한다.

설명은 주석 처리를 하였다.

#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <algorithm>
 
using namespace std;
 
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
 
int main() {
    // 퍼즐의 상태를 string으로 저장한다.
    string s = "";
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            char tmp;
            cin >> tmp;
            s += tmp;
        }
    }
    set<string> chk;
    queue<pair<string, int>> q;
    chk.insert(s);
    q.push(make_pair(s, 0));
 
    int ans = -1;
 
    while (!q.empty()) {
        string now = q.front().first;
        int cnt = q.front().second;
        q.pop();
        // 목표에 도달하였는지 확인
        if (now == "123456780") {
            if (ans == -1 || ans > cnt) ans = cnt; 
        }
        // string에서 0의 위치를 찾는다.
        int start = now.find('0');
 
        // 0의 위치를 2차원으로 표현한다.
        int x = start / 3;
        int y = start % 3;
 
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
                string next = now;
 
                // 2차원으로 표현된 값을 1차원으로 변경
                swap(next[x*3+y], next[nx*3+ny]);
 
                // 방문한 경험이 있는지 확인
                if (chk.find(next) == chk.end()) {
 
                    // 없으면 set에 저장
                    chk.insert(next);
                    q.push(make_pair(next, cnt+1));
                }
            }
        }
    }
    cout << ans << "\n";
}