[Algorithm] 공원 산책

문제 설명

문제 설명

지나다니는 길을 'O', 장애물을 'X'로 나타낸 직사각형 격자 모양의 공원에서 로봇 강아지가 산책을 하려합니다. 산책은 로봇 강아지에 미리 입력된 명령에 따라 진행하며, 명령은 다음과 같은 형식으로 주어집니다.

• ["방향 거리", "방향 거리" … ]

예를 들어 "E 5"는 로봇 강아지가 현재 위치에서 동쪽으로 5칸 이동했다는 의미입니다. 로봇 강아지는 명령을 수행하기 전에 다음 두 가지를 먼저 확인합니다.

• 주어진 방향으로 이동할 때 공원을 벗어나는지 확인합니다.
• 주어진 방향으로 이동 중 장애물을 만나는지 확인합니다.

위 두 가지중 어느 하나라도 해당된다면, 로봇 강아지는 해당 명령을 무시하고 다음 명령을 수행합니다.

공원의 가로 길이가 W, 세로 길이가 H라고 할 때, 공원의 좌측 상단의 좌표는 (0, 0), 우측 하단의 좌표는 (H - 1, W - 1) 입니다.

공원을 나타내는 문자열 배열 park, 로봇 강아지가 수행할 명령이 담긴 문자열 배열 routes가 매개변수로 주어질 때, 로봇 강아지가 모든 명령을 수행 후 놓인 위치를 [세로 방향 좌표, 가로 방향 좌표] 순으로 배열에 담아 return 하도록 solution 함수를 완성해주세요

 

의사코드

1. 입력받은 값을 분리하여 방향(Direction)과 걷는 횟수(WalkCount)를 저장한다.
2. 방향에 따른 이동 좌표값을 Pos 구조체를 선언하여 배열로 미리 만들어 놓는다.
   • West : {0, -1}
   • East : {0, 1}
   • North : {-1, 0}
   • South : {1, 0}
3. [반복문] 이동 명령문을 순회한다.
   1. 이동 명령문에 대해 방향과 걷는 횟수를 저장한다.
   2. 방향에 대한 이동 좌표값을 구한다.
   3. 현재 좌표에서 이동 좌표값을 더한다.
   4. [반복문] 걷는 횟수만큼 반복한다.
      1. 유효성 체크를 한다.
         1. 맵을 벗어났는가?
         2. 장애물을 맞났는가?
      2. 유효하다면 현재 값에 이동 값을 저장한다.
4. 최종적인 이동 값을 반환한다.

 

코드 작성

#include <string>
#include <vector>
#include <map>

using namespace std;

struct Pos
{
    Pos(int y, int x) : y(y), x(x) {}
    int y;
    int x;
};

vector<int> FindStartPostion(const vector<string>& Map)
{
    vector<int> StartPos(2, 0);
    
    for (int y = 0; y < Map.size(); y++)
    {
        for (int x = 0; x < Map[0].size(); x++)
        {
            if (Map[y][x] == 'S')
            {
                StartPos[0] = y;
                StartPos[1] = x;
                return StartPos;
            }
        }
    }
    
    return StartPos;
}

bool CanMove(const vector<string>& Map, int MoveY, int MoveX)
{
    int MapHeight = Map.size();
    int MapWidth = Map[0].size();
    
    if (MoveY >= MapHeight || MoveY < 0)
        return false;
    if (MoveX >= MapWidth || MoveX < 0)
        return false;
    if (Map[MoveY][MoveX] == 'X')
        return false;
    
    return true;
}

vector<int> solution(vector<string> park, vector<string> routes) {
    vector<int> answer = FindStartPostion(park); 
    
    Pos front[4] =
    {
        Pos(0, -1), // West
        Pos(0, 1), // East
        Pos(1, 0), // South
        Pos(-1, 0), // North
    };
    
    map<char, int> DirMap = {
        {'W', 0},
        {'E', 1},
        {'S', 2},
        {'N', 3},
    };
    
    for (string& route : routes)
    {
        char Direction = route[0];
        int WalkCount = route[2] - '0';

        int CurY = answer[0];
        int CurX = answer[1];

        while (WalkCount--)
        {
            Pos MovePos = front[DirMap[Direction]];
            CurY += MovePos.y;
            CurX += MovePos.x;
            
            if (CanMove(park, CurY, CurX) == false)
            {
                break;
            }
        }
        
        if (WalkCount < 0)
        {
            answer[0] = CurY;
            answer[1] = CurX;
        }
    }
    
    return answer;
}