[Softeer/소프티어][level3] 로봇이 지나간 경로 (C++)

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=577

Softeer

 

[난이도] level3
[유형] 백트래킹

[풀이]
먼저 파악해야 할 것이 로봇은 '#' 로 표시된 점 이외에는 절대로 방문하지 않고
한붓그리기 처럼 '#' 점을 한방에 방문해야 합니다.
로봇이 두칸씩 전진하고, 사용한 명령어를 저장해야 하기 때문에 BFS 혹은 DFS 푸는 것은 어렵다고 판단하여
백트래킹을 이용하였습니다.

'#'인 점만 방문하고, 두칸씩 전진함에 따라 많은 경로가 제외되기 때문에 시간내에 해결이 가능합니다.

커맨드를 최소로 하기 위해 어느 점에서 시작해야 최적인지
'#'인 모든 점에 대해 모든 4방향을 시작점으로 백트래킹을 돌려봐야 합니다.

백트래킹 함수 void sol(int y,int x,int d,int cnt,string cmd)
에서 d는 방향, cnt는 현재까지 방문한 '#' 개수, cmd는 현재까지 사용한 커맨드 string입니다.

어떤 점에 도착했을 때 할 수 있는 전진은 총 4가지 입니다.
좌측으로 회전 뒤 전진("LA")
좌측으로 두번 회전 뒤 전진("LLA")
우측으로 한번 회전 뒤 전진("RA") <- ("LLLA)와 같지만 연산 횟수가 역방향으로 돌리는 "RA"가 더 적습니다.
현재 방향으로 전진 ("A")

위 4가지 케이스에 대해 백트래킹 함수를 다시 호출해주면 됩니다.

 

#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int dy[4]={1,0,-1,0};
int dx[4]={0,1,0,-1};
int H,W,ansd,ansy,ansx,sd,sy,sx;
char map[27][27];
bool visit[27][27];
vector<pair<int,int>> cand;
string ret="-1";

void sol(int y,int x,int d,int cnt,string cmd){

    if(cand.size()==cnt){
        if(ret=="-1" || cmd.size() < ret.size()){
            ret=cmd;
            ansy=sy,ansx=sx,ansd=sd;
            ansd=sd;
        }
        return;
    }

    for(int i=0;i<4;i++){
        int nd=(d+i)%4;
        string nxt="A";
        if(i==1) nxt="LA";
        else if(i==2) nxt="LLA";
        else if(i==3) nxt="RA";

        int ny1=y+dy[nd], nx1=x+dx[nd];
        int ny2=y+2*dy[nd], nx2=x+2*dx[nd];

        if(ny2<1||nx2<1||ny2>H||nx2>W) continue;
        if(map[ny1][nx1]!='#' || map[ny2][nx2]!='#' || visit[ny1][nx1] || visit[ny2][nx2]) continue;

        visit[ny1][nx1] = visit[ny2][nx2] = 1;
        sol(ny2,nx2,nd,cnt+2,cmd+nxt);
        visit[ny1][nx1] = visit[ny2][nx2] = 0;
    }
}
int main(){
    scanf("%d%d",&H,&W);
    for(int i=1;i<=H;i++){
        for(int j=1;j<=W;j++){
            scanf(" %c",&map[i][j]);
            if(map[i][j]=='#') cand.push_back({i,j});
        }
    }
    for(auto [y,x] : cand){
        sy=y, sx=x;
        for(int k=0;k<4;k++){
            sd=k;
            memset(visit,0,sizeof(visit));
            visit[y][x]=1;
            sol(y,x,k,1,"");
        }
    }
    char cd = 'v';
    if(ansd==1) cd= '>';
    else if(ansd==2) cd='^';
    else if(ansd==3) cd='<';

    printf("%d %d\n",ansy,ansx);
    printf("%c\n",cd);
    printf("%s",ret.c_str());
}

https://github.com/has2/Problem-Solving/blob/master/softeer/level3/로봇이_지나간_경로.cpp