Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 푸는 슬라이딩 퍼즐: BFS로 최소 이동 횟수 구하기

문제 소개

2x3 크기의 보드가 하나 주어져 있습니다. 보드 위에는 숫자 1부터 5까지 다섯 개의 타일이 놓여 있고, 나머지 한 칸은 빈 칸을 뜻하는 0으로 표시됩니다.

여기서 말하는 '한 번의 이동'이란 0과 상하좌우로 인접한 숫자 하나를 서로 맞바꾸는 것을 의미합니다. 보드의 요소들이 [[1,2,3],[4,5,0]] 형태로 배치되면 퍼즐이 완성된 것입니다.

퍼즐 보드가 주어졌을 때, 목표 상태까지 도달하는 데 필요한 최소 이동 횟수를 구해야 하며, 어떻게 움직여도 퍼즐을 풀 수 없다면 -1을 반환해야 합니다.

예제

예를 들어 입력이 [[1,2,3],[0,4,5]]라면 출력은 2가 됩니다. 먼저 0과 4를 맞바꾼 뒤, 이어서 0과 5를 맞바꾸면 목표 상태에 도달할 수 있기 때문입니다.

풀이 전략: 너비 우선 탐색(BFS)

이 문제는 너비 우선 탐색(BFS)으로 효율적으로 해결할 수 있습니다. 각 보드 상태를 그래프의 노드로, 한 번의 이동으로 도달 가능한 상태를 인접 노드로 간주하면 최소 이동 횟수 구하기는 곧 최단 경로 탐색 문제가 됩니다. BFS는 가까운 상태부터 차례로 탐색하므로, 목표 상태에 처음 도달한 시점의 레벨 값이 바로 최소 이동 횟수입니다.

참고로 2x3 보드에서 가능한 상태는 최대 6! = 720가지에 불과하므로, 모든 상태를 탐색하더라도 계산량이 매우 적습니다.

알고리즘 단계

  1. slidingPuzzle() 함수를 정의하고 보드(board)를 입력으로 받습니다.
  2. 보드가 이미 목표 상태로 정렬되어 있다면 0을 반환합니다.
  3. 2차원 벡터를 담는 큐(q)를 선언하고 초기 보드를 삽입합니다.
  4. 방문한 상태를 기록하는 집합(visited)을 선언하고 초기 보드를 등록합니다.
  5. 큐가 빌 때까지 레벨(lvl)을 1부터 증가시키며 아래 과정을 반복합니다.
    • 현재 큐의 크기를 sz에 저장한 뒤, sz번만큼 반복하며 큐의 맨 앞 상태(node)를 꺼냅니다.
    • node에서 0의 위치(x, y)를 찾습니다.
    • 네 방향(상, 하, 좌, 우) 각각에 대해 다음을 수행합니다.
      • 새 좌표(nx, ny)가 보드 범위를 벗어나면 건너뜁니다.
      • node[x][y]와 node[nx][ny]를 서로 교환(swap)합니다.
      • 교환된 상태가 이미 visited에 존재하면 원래대로 되돌리고 건너뜁니다.
      • 새 상태를 visited에 추가합니다.
      • 새 상태가 목표 상태라면 lvl을 반환합니다.
      • 새 상태를 큐에 삽입한 후, 다시 원래 자리로 되돌립니다.
  6. 큐가 모두 비었는데도 목표 상태에 도달하지 못했다면 -1을 반환합니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
    public:
    bool ok(vector<vector<int>>& b){
        return b[0][0] == 1 && b[0][1] == 2 && b[0][2] == 3 && b[1]
        [0] == 4 && b[1][1] == 5;
    }
    int slidingPuzzle(vector<vector<int>>& board) {
        if (ok(board))
        return 0;
        queue<vector<vector<int> > > q;
        q.push(board);
        set<vector<vector<int> > > visited;
        visited.insert(board);
        for (int lvl = 1; !q.empty(); lvl++) {
            int sz = q.size();
            while (sz--) {
                vector<vector<int> > node = q.front();
                q.pop();
                int x = -1;
                int y = -1;
                for (int i = 0; i < board.size(); i++) {
                    for (int j = 0; j < board[0].size(); j++) {
                        if (node[i][j] == 0) {
                            x = i;
                            y = j;
                            break;
                        }
                    }
                }
                for (int k = 0; k < 4; k++) {
                    int nx = x + dir[k][0];
                    int ny = y + dir[k][1];
                    if (nx < 0 || ny < 0 || nx >= board.size() || ny
                    >= board[0].size())
                    continue;
                    swap(node[x][y], node[nx][ny]);
                    if (visited.count(node)) {
                        swap(node[x][y], node[nx][ny]);
                        continue;
                    }
                    visited.insert(node);
                    if (ok(node))
                    return lvl;
                    q.push(node);
                    swap(node[x][y], node[nx][ny]);
                }
            }
        }
        return -1;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{1,2,3},{0,4,5}};
    cout << (ob.slidingPuzzle(v));
}

입력

{{1,2,3},{0,4,5}}

출력

2

정리

슬라이딩 퍼즐처럼 가능한 상태의 개수가 제한적인 문제는 BFS로 각 상태를 노드처럼 다루면 최소 이동 횟수를 손쉽게 구할 수 있습니다. 방문 처리를 통해 동일한 상태의 중복 탐색을 막는 것이 성능 확보의 핵심이며, 이번 예제에서는 set을 활용해 이를 구현했습니다. 상태마다 0의 위치를 찾아 네 방향으로 확장하는 방식만 익히면, 8퍼즐 등 더 큰 보드에도 동일한 접근법을 그대로 적용할 수 있습니다.