[c++] BOJ 1525 :: 퍼즐

난이도 : 골드 2

걸린 시간 : 1시간

 

문제

퍼즐 문제 바로가기

3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다.

1	2	3
4	5	6
7	8

어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다.

 

풀이

• 최단 경로 문제이므로 bfs 이용
• memo 해야 똑같은 경로 다시 탐색 x
  • memo는 전체 map의 상태를 저장해야함
  • string으로 저장

 

코드

#include <iostream>
#include <string>
#include <unordered_set>
#include <algorithm>
#include <queue>

using namespace std;

int map[10];
unordered_set<string> memo;
int direction[9][4] = { {-1,1,3,-1}, {-1,2,4,0}, {-1,-1,5,1}, {0,4,6,-1}, {1,5,7,3}, {2,-1,8,4}, {3,7,-1,-1}, {4,8,-1,6}, {5,-1,-1,7} };

struct Node {
    int zero;
    string mapstring;
    int move = 0;
    Node(int z, string s, int m) {
        zero = z;
        mapstring = s;
        move = m;
    }
};

int main() {
    int zero = -1;
    string mapString = "";
    for (int i = 0; i < 9; i++) {
            string tmp = "";
            cin >> tmp;
            mapString += tmp;
            if (tmp == "0")
                zero = i;

    }
    if (mapString == "123456780") {
        cout << 0;
        return 0;
    }
    queue<Node*> que;
    que.push(new Node(zero, mapString, 0)); memo.insert(mapString);
    while (!que.empty()) {
        Node* z = que.front(); que.pop();
        for (int i = 0; i < 4; i++) {
            if (direction[z->zero][i] == -1)
                continue;
            int zeroSpot = z->zero; string tmpMapString = z->mapstring; int tmpMove = z->move +1;
            int newZero = direction[z->zero][i];
            tmpMapString[z->zero] = tmpMapString[newZero];
            tmpMapString[newZero] = '0';

            if (tmpMapString == "123456780") { // 정답
                cout << tmpMove;
                return 0;
            }

            auto pos = memo.find(tmpMapString);
            if (pos != memo.end())// memo에 있다면 (방문 했던 곳이면)
                continue;

            que.push(new Node(newZero, tmpMapString, tmpMove));
            memo.insert(tmpMapString);
        }
    }
    cout << -1;
}

memo는 unordered_set을 이용해서 string으로 판단

 

주의할 점

• dfs로 하면 스택 오버플로우
• 처음에 정답이 넘어오는 경우 0을 출력해주어야 함

 

결과

아이디	메모리	시간	언어	코드 길이
gmldms784	27780	192	C++17 / 수정	2553