[프로그래머스 Level 3] 미로 탈출 명령어 (C++)

코딩테스트 연습 - 미로 탈출 명령어 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

처음엔 무작정 bfs로 구현하고 시간을 줄일 수 있는 방법을 찾아보기로 헀다.

처음 생각한 방법은 현재까지 이동한 거리와 현 위치에서 도착지까지의 거리의 합이 k보다 크면 k안에 도착할 수 없으므로 해당 queue는 버리는 방법이다. -> 시간 초과

두 번째 방법은 사전 순서이므로 d->l->r->u 순으로 값이 순서대로 들어가도록 하는 것이다. -> 첫 번째 방법과 비교했을 때 큰 차이 없음.

세 번째 방법은 우선 순위 큐를 이용하여 사전 순서로 가장 빠른 것 먼저 연산을 수행하도록 했다. -> 맨 마지막 테케만 시간 초과

마지막은 정 모르겠어서 질문하기를 참고했고, k가 짝수일 때 남은 거리가 홀수이면 안 되는 것을 조건으로 넣어줬다. (제공 테케의 마지막 테케 참고)

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <memory.h>

using namespace std;

struct cmp{
        bool operator()(pair<pair<int,string>,pair<int,int>> a,pair<pair<int,string>,pair<int,int>> b){
            return a.first.second>b.first.second;
        }
};

//이동한 거리, 이동현황, x, y
priority_queue<pair<pair<int, string>, pair<int,int>>, vector<pair<pair<int,string>,pair<int,int>>> ,cmp> q;
string v;
//d -> l -> r -> u 순서로 빠르다.
int moveX[4] = {0,-1,1,0};
int moveY[4] = {1,0,0,-1};
char dir[4] = {'d', 'l', 'r', 'u'};

string solution(int n, int m, int x, int y, int r, int c, int k) {
    string answer = "";
    
    q.push({{0,""},{x,y}});
    while(!q.empty()){
        int n1 = q.top().first.first;
        string s1 = q.top().first.second;
        int n2 = q.top().second.first; // y
        int n3 = q.top().second.second; // x
        q.pop();
        if(n2==r&&n3==c&&n1==k){
            v=s1;
            break;
        }
        int sum = abs(r-n2)+abs(c-n3);
        if(k%2==0 && (n1+sum)%2==1){
            continue;
        }
        if(n1+sum>k){
            continue;
        }else{
            for(int i = 0; i<4; i++){
                int movedY = moveY[i]+n2;
                int movedX = moveX[i]+n3;
                if(movedX>0&&movedX<=m&&movedY>0&&movedY<=n){
                    q.push({{n1+1, s1+dir[i]},{movedY, movedX}});
                }
            }
        }
    }
    if(v.empty())
        return "impossible";
    return answer=v;
}

int main() {
    string answer = solution(3,4,2,3,3,1,5);
    cout<<answer<<endl;
    return 0;
}