미로탈출 명령어

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

/*
[입력]
격자 사이즈(n,m)
시작점 (x,y)
도착점(r,c)
이동거리k


[로직]
1. bfs로 거리 측정 distance, 문자열도 저장해야됨
2. k가 짝수면 추가 계산 가능 홀수면 추가 계산 불가능
3. 제일 짧은 거리 수 만들기 짧은 순으로 검사하면 어짜피 bfs가 최단거리 구하는거라서 최단거리로 구해짐
    1. 우선순위목록
    d(dududu) -100   하상
    l(lrlrlr) - 108  좌우
    r(rlrlrl) - 114  우좌
    u(ududud)- 117   상하
    
    

[출력]
탈출 경로의 문자(문자열이 가장 빠른 순으로 d - l -r -u)

*/

int N, M, X, Y, R, C, K;
int dx[] = {1, 0, 0, -1}; // d, l, r, u 순서로 이동
int dy[] = {0, -1, 1, 0};
char letters[] = {'d', 'l', 'r', 'u'};

bool visited[55][55][2501];

struct Pos {
    int x, y, dist;
    string path;
    Pos(int xv, int yv, int distv, string str) : x(xv), y(yv), dist(distv), path(str) {}
};

string solution(int n, int m, int x, int y, int r, int c, int k) {
    N = n; M = m; X = x; Y = y; R = r; C = c; K = k;

    //거리를 뺸게 홀수면 와리가리 못해서 무조건 실패임
    int requiredMoves = abs(R - X) + abs(C - Y);
    if (requiredMoves > K || (K - requiredMoves) % 2 != 0) return "impossible";

    queue<Pos> q;
    q.push(Pos(X, Y, 0, ""));
    visited[X][Y][0] = true;

    while (!q.empty()) {
        Pos cur = q.front();
        q.pop();

        if (cur.dist == K) {
            if (cur.x == R && cur.y == C) return cur.path;
            continue;
        }

        for (int dir = 0; dir < 4; ++dir) {
            int nx = cur.x + dx[dir];
            int ny = cur.y + dy[dir];
            int nextDist = cur.dist + 1;
            string nextPath = cur.path + letters[dir];

            if (nx < 1 || ny < 1 || nx > N || ny > M) continue;
            if (visited[nx][ny][nextDist]) continue; //지나간곳이면 skip -어짜피 제일 빠른애가 지나간거임 
            //대신 지금 5번 지나가는중인데 4번째 지나간곳은 지나갔고 5번째는 안지나갔다?
            //그러면 5번째에 지나갈 수 있는거임
            

            visited[nx][ny][nextDist] = true;//
            q.push(Pos(nx, ny, nextDist, nextPath));
        }
    }

    return "impossible";
}

생각보다 어려웠다 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

아이디어

1. 어짜피 bfs는 제일 빠른 순으로 돈다.

어짜피 최단거리를 탐색한다. 그러니까 동서남북 탐색 순서를 사전 순으로 배치해버리면 된다. 그러면 최단 거리를 탐색하게 되는 것

2. 각 격자 사이의 거리를 뺀게 홀수면 무조건 불가능함

이게 무슨의미냐

애초에 K값이 5라고 가정하고 맵에서 시작점 -> 끝점으로 가는 최단 경로에서 3을 이동해야한다고 가정하자
그러면 5-3 -> 2가 남는데 이 2는 와리가리할때 사용한다.
그러니까 남는 거리일 때 무조건 좌우던 상하던 왔다 갔다를 해야하는데 이게 홀수면 도착점에 도달을 할 수가 없다.

그래도 생각보다 빠르게 이해하고 접근할 수 있어서... 다행이었다... 물론 gpt도움을 많이 받긴 했지만...
근데 나 레벨 4는 도저히 풀 자신이 없다 ㅠ

REVIEW

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL