백준 1525 퍼즐

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

불러오는 중입니다...

메모리도 정말 적게 주고 정말 난감한 문제입니다. 처음에 문제를 풀 때 재귀를 써서 해볼까 생각했는데

탈출 조건이 명확하지 않았습니다. 그 이유는 맞출 수 없는 퍼즐인 경우에 계속 깊어질 수 있다는 점이

생기게 되어 bfs를 이용해서 돌려야 하는데 재귀같이 이전의 맵을 저장 해서 돌리고 싶었는데 

그게 쉬운 것만은 아녔습니다. 

그래서 이용한 방법이 map() 함수와 string을 이용한 방법이었습니다.

map 함수에 대해서 간단히 설명드리자면 원소를 key와 value 쌍으로 저장을 하는 것으로

맵 자체를 key로 해서 체크를 간편하게 할 수 있습니다.

 

0을 9로 바꾸어 123456789라는 키값이 되었을 때 그 키값에 얼마나 저장되어있는지 출력하면 되는 것입니다.

3  * 3 이차원 배열을 이차원인 string으로 만들고 

find() 함수를 이용하여 현재 9의 위치 즉 0의 위치를 찾습니다.

그리고 여기서 

이렇게 한이유는 

#include<stdio.h>
#include<string>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
string s;
string e = "123456789";
queue<string> q;
map<string, int> visit;
void init() {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            char a;
            scanf(" %1c",&a);
            if (a == '0')a = '9';
            s.push_back(a);
        }
    }
}
int main(void) {
    init();
    q.push(s);
    visit[s] = 0;
    while (!q.empty()) {
        string c = q.front(); q.pop();
        if (c == e) {
            break;
        }
        int zero_pos = c.find('9');
        int y = zero_pos / 3;
        int x = zero_pos % 3;
        for (int d = 0; d < 4; d++) {
            int ny = y + dy[d];
            int nx = x + dx[d];
            if (0 <= ny && ny < 3 && 0 <= nx && nx < 3) {
                string t = c;
                swap(t[y * 3 + x], t[ny * 3 + nx]);// 갈수 있는 위치
                if (!visit.count(t)) {//한번 도 나온 경우가 아니라면
                    visit[t] = visit[c] + 1;
                    q.push(t);
                }
            }
        }
    }
    if (!visit.count(e)) {
        printf("-1\n");
    }
    else {
        printf("%d\n", visit[e]);
    }
    return 0;
}