[BFS] 1525번 퍼즐

1525번 퍼즐

 

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

 

문제

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

1	2	3
4	5	6
7	8

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

1		3
4	2	5
7	8	6

1	2	3
4		5
7	8	6

1	2	3
4	5
7	8	6

1	2	3
4	5	6
7	8

가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오.

 

입력

세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.

 

출력

첫째 줄에 최소의 이동 횟수를 출력한다. 이동이 불가능한 경우 -1을 출력한다.

 

예제 입력

1 0 3
4 2 5
7 8 6

 

예제 출력

3

 

해결방법

처음 문제를 보고 들었던 생각은

• DFS + 백트래킹으로 완전 탐색을 진행해야하나?? → Limit점이 존재하지않음...
• BFS 탐색?? → 배열이 하나인데 큐에 어떻게 정보를 담지???

 

그러다가 한 블로그에서 힌트를 얻었다

3x3 배열을 문자열로 큐에 담는 법이었다. BFS 탐색은 아래와 같이 진행된다

            1 0 3
            4 2 5
            7 8 6
     ↙︎        ↓       ↘︎
   0 1 3    1 2 3    1 3 0
   4 2 5    4 0 5    4 2 5
   7 8 6    7 8 6    7 8 6

 

 

퍼즐을 이동하는 함수는 아래와 같다

일단 tmp 배열을 준비한 다음, map 배열에 복사를 해준다

그 과정에서 0 또는 swap 대상인 노드를 만나면 서로 swap 을 진행한다

string movePuzzle(int x,int y){
    string str = "";
    int num = map[x][y];
    
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            if(map[i][j] == 0) tmp[i][j] = num;
            else if(map[i][j] == num) tmp[i][j] = 0;
            else tmp[i][j] = map[i][j];
            str += (tmp[i][j] + '0');
        }
    }
    return str;
}

 

아무 문제없이 코드를 작성하다 한가지 문제가 생겼다

BFS 탐색에서는 이미 방문한 노드를 다시 방문하지 않도록 visited 배열을 사용했다

하지만 여기서는 string 을 가지고 중복 처리를 해야한다

 

따라서 Set 을 사용해야 했다

중복이 허용되지 않는 Set의 특징을 이용한 풀이였다

// set 의 find() 메소드를 통해 중복되지 않은 값이라면 진행
if(visited.find(puz) == visited.end()){
    q.push(puzzle(puz,cnt+1));
    visited.insert(puz);
}

 

시간복잡도는 3x3 퍼즐이 총 9! 의 상태를 가질 수 있고 Set을 통한 중복검사에 log N 만큼의 시간이 든다

따라서 O(9! + log (9!)) 의 시간복잡도를 가진다

 

 

소스코드

[ 2차원 배열을 사용한 Code ]

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <queue>
#include <algorithm>
#include <set>
#define MAX 0
#define INF 987654321
using namespace std;
typedef pair<int, int> node;

struct puzzle {
    string str;
    int cnt;
    
    puzzle() { }
    puzzle(string _str, int _cnt) : str(_str), cnt(_cnt) { }
};

int ans;
int map[3][3], tmp[3][3];

int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};

set<string> visited;

string movePuzzle(int x,int y){
    string str = "";
    int num = map[x][y];
    
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            if(map[i][j] == 0) tmp[i][j] = num;
            else if(map[i][j] == num) tmp[i][j] = 0;
            else tmp[i][j] = map[i][j];
            str += (tmp[i][j] + '0');
        }
    }
    return str;
}

void bfs(puzzle s){
    queue<puzzle> q;
    q.push(s);
    visited.insert(s.str);
    
    while(!q.empty()) {
        string state = q.front().str;
        int cnt = q.front().cnt;
        q.pop();
        
        if(state.compare("123456780") == 0){
            cout << cnt << "\n";
            return;
        }
        
        node zero;

        // String -> Arr[][] 변환
        // '0' 의 위치를 찾음
        int ind = 0;
        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                map[i][j] = state[ind++] - '0';
                
                if(map[i][j] == 0) zero = node(i,j);
            }
        }
        
        // 4방향 탐색 후 BFS 진행
        for(int i=0; i<4; i++){
            int nx = zero.first + dx[i];
            int ny = zero.second + dy[i];
            
            if(nx<0 || ny<0 || nx>=3 || ny>=3) continue;
            
            string puz = movePuzzle(nx,ny);
            
            // set 의 find() 메소드를 통해 중복되지 않은 값이라면 진행
            if(visited.find(puz) == visited.end()){
                q.push(puzzle(puz,cnt+1));
                visited.insert(puz);
            }
        }
    }
    cout << -1 << "\n";
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    string initial_state = "";
    int num;
    
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            cin >> num;
            initial_state += (num + '0');
        }
    }
    
    bfs(puzzle(initial_state,0));
    
}

[ Vector를 사용한 Code ]

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <algorithm>
#define MAX 0
#define INF 987654321
using namespace std;

typedef pair<int, int> point;

struct puzzle {
    string state;
    int cnt;
    
    puzzle() { }
    puzzle(string _state,int _cnt) : state(_state), cnt(_cnt) { }
};

int ans;
vector<vector<int>> map(3,vector<int>(3,0));

int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};

set<string> visited;

point findZero(vector<vector<int>> now){
    point zero;
    
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            if(now[i][j] == 0){
                zero.first = i;
                zero.second = j;
            }
        }
    }
    return zero;
}

string movePuzzle(vector<vector<int>> now,point zero,int ind){
    string str;
    
    int nx = zero.first + dx[ind];
    int ny = zero.second + dy[ind];
    
    if(nx<0 || ny<0 || nx>=3 || ny>=3) return "";
    
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            if(now[i][j] == 0)
                str += (now[nx][ny] + '0');
            else if(now[i][j] == now[nx][ny])
                str += "0";
            else
                str += (now[i][j] + '0');
        }
    }
    return str;
}

vector<vector<int>> strToVector(string str){
    vector<vector<int>> tmp(3,vector<int>(3));
    
    int ind = 0;
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            tmp[i][j] = str[ind++] - '0';
        }
    }
    return tmp;
}

void bfs(string initialState){
    queue<puzzle> q;
    q.push(puzzle(initialState,0));
    visited.insert(initialState);
    
    while(!q.empty()){
        string state = q.front().state;
        int cnt = q.front().cnt;
        q.pop();
        
        if(state == "123456780"){
            cout << cnt << "\n";
            return;
        }
        
        vector<vector<int>> nPuzzle(3,vector<int>(3));
        nPuzzle = strToVector(state);
        point zero = findZero(nPuzzle);
        
        for(int i=0; i<4; i++){
            string moveState;
            moveState = movePuzzle(nPuzzle,zero,i);
            
            if(moveState == "") continue;
            
            if(visited.find(moveState) == visited.end()){
                q.push(puzzle(moveState,cnt+1));
                visited.insert(moveState);
            }
        }
    }
    cout << -1 << "\n";
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    string initialState = "";
    
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            cin >> map[i][j];
            initialState += (map[i][j] + '0');
        }
    }
    
    bfs(initialState);
}