[백준/Baekjoon] 1525 퍼즐 C++ :: BFS & Set & Map

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

1525번: 퍼즐

---

1. Logic

입력을 인덱스로도 받지만 string으로 받은 후 0의 위치를 찾고 그 상태에서 옮길 수 있는 좌표를 찾아 BFS 브루트포싱한다. 방문처리를 어떻게 해야 할 지 고민이었는데 map / set을 활용하여 중복이 되지 않도록 처리해줬다. 

 

map을 활용한 풀이, set을 활용한 풀이 둘 다 해봤다

---

2. Code

map을 활용한 풀이

#include <bits/stdc++.h>

using namespace std;

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

int graph[3][3];
map<string, int> m;

string str = "";
const string answer = "123456780";


int bfs() {
    queue<string> q;
    q.push(str);
    
    while(!q.empty()) {
        string curState = q.front();
        
        q.pop();
        
        if(curState == answer) {
            return  m[curState];
        }
        
        int zero = curState.find('0');
        int x = zero / 3;
        int y = zero % 3;
        
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx < 0 || ny < 0 || nx >= 3 || ny >= 3) continue;
            
            string temp = curState;
            
            swap(temp[3*x + y], temp[3*nx+ny]);
            
            if(!m[temp]) {
                m[temp] = m[curState] + 1;
                q.push(temp);
            }
        }
    }
    return -1;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            cin >> graph[i][j];
            str += (graph[i][j] + '0');
        }
    }
    
    cout << bfs();
}

 

set을 활용한 풀이

#include <bits/stdc++.h>

using namespace std;

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

int graph[3][3];

unordered_set<string> s;

string str = "";
const string answer = "123456780";


int bfs() {
    queue<pair<string, int>> q;
    q.push({str, 0});
    
    while(!q.empty()) {
        string curState = q.front().first;
        int cnt = q.front().second;
        q.pop();
        
        if(curState == answer) {
            return cnt;
        }
        
        int zero = curState.find('0');
        int x = zero / 3;
        int y = zero % 3;
        
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx < 0 || ny < 0 || nx >= 3 || ny >= 3) continue;
            
            string temp = curState;
            
            swap(temp[3*x + y], temp[3*nx+ny]);
            
            if(s.find(temp) == s.end()) {
                s.insert(temp);
                q.push({temp, cnt+1});
            }
        }
    }
    return -1;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            cin >> graph[i][j];
            str += (graph[i][j] + '0');
        }
    }
    
    cout << bfs();
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐