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

🔗문제

1525번: 퍼즐

1525번: 퍼즐

 

🖍풀이

한칸이 비워져있는 퍼즐을 순서대로 정렬하기 위한 최소 이동 비용을 구하는 문제

 

빈칸을 기준으로 사방의 셀을 옮겨가며 BFS방식으로 풀 수 있다.

 

 

---

 

 

🚩 2차원 배열이 아니라 문자열로 표현

 

빈칸을 기준으로 사방의 셀을 이동한다면 당연히 2차원 배열을 생각할 수 있지만, 이 풀이에서는 일련의 문자열로 취급해서 풀어주었다.

 

문자열에서 n 번째에 있는 빈칸을 x, y로 표현하는 법

 

문자열로 된 퍼즐을 BFS에 활용하는 법

최소 이동횟수를 구해야하기 때문에 이미 형성된 퍼즐을 큐에 넣으면 안된다.

map이나 set를 활용하자.

// 전에 탐색했던 퍼즐모양과 같지 않으면 큐에 넣는다
if(visited.find(swabed) == visited.end())
{
    q.push(std::make_pair(swabed, time+1));
    visited.insert(swabed);
}

 

+)

BFS로 풀고 visited의 컨테이너를 세 조합으로 짜봤는데 2가 가장 빨랐다.

• queue<숫자> + map<숫자> (value)
• queue<숫자, 이동 횟수> + set<숫자> (bool)
• queue<숫자> + set<숫자> (이동 횟수는 qSize만큼 while문 돌려 해결)

---

 

도움된 반례

1 2 3
4 5 0
6 7 8
//정답: 13

🔗 https://www.acmicpc.net/board/view/92488

 

💾 소스

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

const std::string ANSWER = "123456780";
char tmp;

bool isValid(const int r, const int c)
{
    if(r<0 || c<0 || r>=3 || c>=3 )
        return false;

    return true;
}

int BFS(const std::string& initial)
{
    
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    
    //현재 퍼즐 상태와 이동 횟수
    std::queue<std::pair<std::string, int> > q;
    q.push(std::make_pair(initial, 0));

    // 퍼즐 상태가 문자열로 되어있기 때문에 set을 이용하여 재방문 확인
    std::set<std::string> visited;
    visited.insert(initial);

    std::string puzzle, swaped;
    int time = 0;
    
    while(!q.empty())
    {
        puzzle = q.front().first;
        time = q.front().second;
        q.pop();

        if(puzzle == ANSWER)
        {
            return time;
        }
 
        // 빈칸의 위치를 찾아서 x, y 위치를 파악
        int zero = puzzle.find('0');
        int zx = zero/3;
        int zy = zero%3;

        for(int d=0; d<4; ++d)
        {
            int x = zx + dx[d];
            int y = zy + dy[d];

            if(!isValid(x, y)) continue;

            //swab
            swaped = puzzle;
            tmp = swaped[zero];
            swaped[zero] = swaped[x* 3 + y];
            swaped[x* 3 + y] = tmp;

            // 전에 탐색했던 퍼즐모양과 같지 않으면 큐에 넣는다
            if(visited.find(swaped) == visited.end())
            {
                q.push(std::make_pair(swaped, time+1));
                visited.insert(swaped);
            }
        }
    }
    
    return -1;
}

int main()
{
    std::string puzzle;
    puzzle.resize(9);

    for(int i=0; i<9; ++i)
    {
        std::cin >> tmp;
        puzzle[i] = tmp;
    }
    
    std::cout << BFS(puzzle);

    return 0;
}