[2023 KAKAO BLIND RECRUITMENT] 미로 탈출 명령어

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

프로그래머스

2023 KAKAO BLIND RECRUITMENT 미로 탈출 명령어 문제입니다

 

문제는 시작지점에서 도착지점이 있는 정해진 공간의 미로에서 탈출하는 문제입니다

여기까지는 최단거리를 구하는 문제이지만 몇가지 조건이 추가됩니다

 

1. 격자의 밖으로는 이동할 수 없습니다

2. 출발지점에서 도착지점까지 이동거리는 총 K여야합니다 (모든 격자를 두 번 이상 방분해도 됩니다)

3. 미로를 탈출한 경로를 문자열로 나타냈을 때, 사전순으로 가장 빠른 경로로 탈출해야합니다.

 

문제의 이해

....
..S.
E...

가로 4 세로 3인 3X4 격자입니다 K(이동거리)는 5입니다
.은 빈공간 S는 출발지점 E는 도착지점입니다

이때 위의 조건을 만족하면서 이동거리 K가 5인 탈출 경로는

사전순으로 d l r u이 빠르기때문에

down ㅡ> left  ㅡ> left ㅡ> right ㅡ> left

dllrl입니다

초록이 도착지점 빨강은 현재 위치

 

문제의 접근

사전순으로 가장 빠른 경로라는 말에서 부르트 포스로 접근하기로 마음먹었습니다

2차원 미로를 설정하고 배열에 도착지점부터의 거리를 계산해서 넣어줌으로써 사전순으로 미로를 이동하다가 K = 남은이동횟수에 도달했을때 도착지점까지 이동할 수 있도록 설계를 해보았습니다

 

해당 문제를 풀기위해

1. 2차원 배열에 미로데이터를 넣어줍니다

2. 사전순서로 빠른방향부터 이동을 합니다

3. 도착지점까지 남은 이동을 진행해줍니다

4. 가능 불가능 여부 판단

 

1. 2차원 배열에 미로데이터를 넣어줍니다

변수 2개를 선언하여 시작지점과 도착지점의 x,y, 값을 설정하고, 2차원 배열을 선언한후 도착지점에서 각 지점 사이의 거리를 계산하여 입력해줍니다.

 

2. 사전순서로 빠른방향부터 이동을 합니다

문제의 조건인  사전순으로 빠른 경로로 탈출을 하기 위해서  배열에 할당된 거리가 < 남은 이동거리 가 아니라면 사전순서에 우선하여 이동을 진행합니다.

3. 도착지점으로 강제 이동

결국은 위 아래, 왼쪽 오른쪽 둘중 하나의 방향으로 이동할태니까 이부분을 계산하여 남은 문자열을 추가해줍니다.

 

4. 가능 불가능 여부 판단

만일 불가능한 경우 정답 배열의 크기가 문제에서 주어진 K와 같을수가 없습니다 때문에 K = answer.size()와 비교하여 가능 불가능여부를 판단합니다.

 

#include <iostream>
#include <string>
#include <cstring>
#include <vector>


using namespace std;

string solution(int n, int m, int x, int y, int r, int c, int k) {
    string answer = "";
    int map[53][53];
    memset(map, -1, sizeof(map));
    map[r][c] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            map[i][j] = abs(r - i) + abs(c - j);
        }
    }
    
    int currentX = x, currentY = y, availalbeMoves = k;
    for (int i = 0; i < k; i++) 
    {
        if (map[currentX][currentY] < availalbeMoves)
        {
            availalbeMoves--;
            if(map[currentX+1][currentY] != -1)
            {
                currentX++;
                answer += "d";
            }
            else if (map[currentX][currentY-1] != -1)
            {
                currentY--;
                answer += "l";
            }
            else if (map[currentX][currentY+1] != -1)
            {
                currentY++;
                answer += "r";
            }
            else if (map[currentX-1][currentY] != -1)
            {
                currentX--;
                answer += "u";
            }
        }
    }
    
    if (availalbeMoves != 0)
    {
        if (currentX <= r)
        {
            int count = n - currentX;
            for (int i = 0; i < count; i++)
            {
                answer += "d";
            }
        }
        if (c <= currentY)
        {
            int count = currentY - c;

            for (int i = 0; i < count; i++)
            {
                answer += "l";
            }
        }
        else
        {
            int count = c - currentY;
            for (int i = 0; i < count; i++)
            {
                answer += "r";
            }
        }
        if (r < currentX)
        {
            int count = currentX - r;
            for (int i = 0; i < count; i++)
            {   
                answer += "u";
            }
        }
    }
    if(answer.size()!=k)
    {
        answer = "impossible";
    }
    return answer;
}