백준 1525 / 퍼즐

나올 수 있는 경우의 수가 총 9!.

그러나 현 퍼즐의 상태를 저장하기 위해선 (빈칸이 0이라 가정하고) 

최대 876543210 짜리 배열이 필요하다. (약 4기가) 무조건 메모리초과가 난다.

이 문제를 해결하기 위해선 map이란 클래스가 필요하다.

map은 쉽게 생각해서 map["string"]이나 map[92342384023] 같은 일반적인 배열이 할 수 없는 것들을 가능하게 하는 자료구조다. 

(    )

문제에서 사용된 map의 기능은 count. 

map.count("바보")는 "바보"란 스트링이 한번이라도 들어갔으면 1, 들어간 적이 없으면 0을 출력하는 기능이다.

(BFS 문제에 자주 사용되는 부울 배열의 기능과 같다.)

또한 코드는 string의 기능을 잘 이용해야 쉽게 풀 수 있다.

string.find('3')은 string에서 3이 몇번째 인덱스에 있는지 출력하고.

swap(string[3],string[4])은 3번째 값과 4번째 값을 바꾸어주는 함수다.

이 기능들을 사용하면 문제를 해결할 수 있다.

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<string>
 
using namespace std;
 
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
 
int main() {
    //freopen("Text.txt", "r", stdin);
 
    int start = 0;
 
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            int tmp;
            cin >> tmp;
            if (tmp == 0) {
                tmp = 9;
            }
            start = start * 10 + tmp;
        }
    }
 
    queue<int>q;
    map<int, int>dist;
    dist[start] = 0;
 
    q.push(start);
    
    while (!q.empty()) {
        int now = q.front();
        string snow = to_string(now);
        q.pop();
 
        int z = snow.find('9');
        int x = z / 3;
        int y = z % 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) {
                string next = snow;
                swap(next[z], next[nx * 3 + ny]);
 
                int num = stoi(next);
                if (dist.count(num) == 0) {
                    dist[num] = dist[now] + 1;
                    q.push(num);
                }
            }
        }
 
    }
 
    if (dist.count(123456789) == 0) {
        cout << -1 << endl;
    }
    else {
        cout << dist[123456789];
    }
}