백준, BOJ, 1525번, 퍼즐 C++ [CPP] ★★★★★

 

나의 좁은 식견에 안타까워하며

배운 상태 저장방법!!

 

행렬을 문자열로 문자열을 행렬로 변환하는 방법!!

행렬 자체를 저장하는 것이 메모리가 많이드므로 

문자열로 저장하는 방법!!!

배울 것이 많은 문제다.

 

 

 

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

 

---

 

#맞은 풀이

#include<bits/stdc++.h>

using namespace std;

int dc[4] = {1,-1,0,0};
int dr[4] = {0,0,1,-1};


string start = ""; //상태를 문자열로 저장함
int answer = -1; //answer가 갱신되지 않는 것은 아무리 시도해도 만들 수 없는 것을 의미


int main(){
    
    
    
    queue<pair<string, int>> q; //string(상태), int(실행횟수)
    set<string> check; //상태가 중복되는 것을 허용하지 않음(최단거리)
    
    //초기 상태 입력
    for(int i = 0; i<3; i++){
        for(int j = 0; j<3; j++){
            char x;
            cin >> x;
            start += x;
        }
    }
    
    //초기 상태와 실행횟수를 집어넣음으로써 시작
    q.push({start, 0});
    check.insert(start);
    
    while(!q.empty()){
        auto cur = q.front();
        q.pop();
        string state = cur.first;
        int countTry = cur.second;
        
        //목표 상태에 도달했을 때
        if(state == "123456780" && (answer == -1 || answer > countTry)){
            answer = countTry;
        }
           
        int curPos = state.find('0'); //0의 위치(인덱스)
        
        //행의 위치는 몫, 열의 위치는 나머지 (col,row)
        // -> 4 * 3이라면..? 4로 나누고 3으로 나눈 나머지가 된다.
        int col = curPos / 3;
        int row = curPos % 3;
        //해당위치에서 동서남북 4가지 방향으로 자리를 바꾸어서 큐에 넣어준다.
        for(int dir = 0; dir<4; dir++){
            int nc = col + dc[dir];
            int nr = row + dr[dir];
            
            //범위체크
            if(nr<0 || nr>= 3 || nc<0 || nc >= 3)continue;
            //방문체크는 하지 않음 -> 어차피 같은 상태면 -> set에 있을 것이기 때문
            
            //state를 바꿔야함 -> 행, 열 성분을 다시 문자 성분으로 바꿈.
            string curState = state;
            
            //현위치, 다음 위치를 바꿈.
            swap(curState[col*3 + row], curState[nc*3 + nr]);
            
            //curState는 위치를 바꾼 상태로 남아있음
            //중복된 상태는 넣지 않음. 최초의 상태만 넣음 -> 중복된 상태를 넣게되면 큐가 끝나지 않음.
            //-> 아무리 해도 만들어지지 않으면 큐가 비워짐 while문 종료
            if(check.count(curState) == 0){
                check.insert(curState);
                q.push({curState, countTry+1});
            }
        }

    }
    
    cout << answer;
    
    return 0;
}

 

 

비슷한 문제를 다시 풀어보면서 익혀야겠다.

상태를 저장한다는 것이 정말 좋다.