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

https://school.programmers.co.kr/learn/courses/30/lessons/150365

프로그래머스

풀이

BFS와 3차원 방문 체크 배열을 사용해서 문제를 해결할 수 있다.

1. 명령어는 오름차순 중 가장 첫번째 명령어를 출력해야 하므로 "d, l, r, u" 순서로 방문을 진행한다.

2. 방문 체크 배열은 거리 정보를 저장하는 3차원 배열이다.

3. 체크 배열로 같은 지점을 같은 거리로 도착하는 우선순위가 나중인 명령어를 중복으로 큐에 넣는 것을 방지한다.

리뷰

2번 이상 중복 방문이 가능해서 체크 배열을 사용하지 않고, 거리 조건에 따라 break하는 코드를 구현했더니 당연히 시간초과다. 탐색 우선순위를 결정하고, 우선 순위가 나중인 경로의 중복 방문을 막기 위한 3차원 체크 배열을 사용해야 하는 문제였다.

#include <string>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

// d, l, r, u
int dr[4]={1, 0, 0, -1};
int dc[4]={0, -1, 1, 0};

struct Info{
    int row, col;
    string cmd;
    Info (int a, int b, string c){
        row=a;
        col=b;
        cmd=c;
    }
};

string solution(int n, int m, int x, int y, int r, int c, int k) {
    string answer = "";
    
    bool ch[n+1][m+1][k+1];
    memset(ch, false, sizeof(ch));
    
    queue<Info> q;
    q.push(Info(x, y, ""));
    while (!q.empty()){
        Info v=q.front();
        q.pop();
        
        if (v.row==r && v.col==c){
            if (v.cmd.length()==k) return v.cmd;
        }
        if (v.cmd.length()==k) continue;
        for (int i=0; i<4; i++){
            int nr = v.row+dr[i];
            int nc = v.col+dc[i];
            if (nr<1 || nr>n || nc<1 || nc>m || ch[nr][nc][v.cmd.length()+1]) continue;
            string c="";
            if (i==0) c=v.cmd+"d";
            if (i==1) c=v.cmd+"l";
            if (i==2) c=v.cmd+"r";
            if (i==3) c=v.cmd+"u";
            ch[nr][nc][v.cmd.length()+1]=true;
            q.push(Info(nr, nc, c));
        }
    }
    
    return "impossible";
}