프로그래머스 - 수레 움직이기

프로그래머스 수레 움직이기 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

n * m 크기 격자 모양의 퍼즐판이 주어집니다.
퍼즐판에는 빨간색 수레와 파란색 수레가 하나씩 존재하며 각 수레들은 자신의 시작 칸에서부터 자신의 도착 칸까지 이동해야 합니다.
모든 수레들을 각자의 도착 칸으로 이동시키면 퍼즐을 풀 수 있습니다.
각 턴마다 반드시 모든 수레를 상하좌우로 인접한 칸 중 한 칸으로 움직여야 합니다. 단, 수레를 움직일 때는 아래와 같은 규칙이 있습니다.

• 수레는 벽이나 격자 판 밖으로 움직일 수 없습니다.
• 수레는 자신이 방문했던 칸으로 움직일 수 없습니다.
• 자신의 도착 칸에 위치한 수레는 움직이지 않습니다. 계속 해당 칸에 고정해 놓아야 합니다.
• 동시에 두 수레를 같은 칸으로 움직일 수 없습니다.
• 수레끼리 자리를 바꾸며 움직일 수 없습니다.
  퍼즐을 푸는데 필요한 턴의 최소값을 구해야합니다.

문제 풀이

1 <= n, m <= 4이므로 최대 퍼즐판의 크기가 작은 편에 속합니다.
그러므로 위의 규칙을 지키며 빨간색 수레가 도착 칸까지 가는 이동 경로들과 파란색 수레가 도착 칸까지 가는 이동 경로들을 계산 후, 각 경우들이 이동 가능한지 확인해주면 쉽게 답을 구할 수 있습니다.

제가 풀어낸 방식은 재귀를 사용하여 먼저 빨간색 수레의 이동 경로를 구한 후 파란색 수레의 이동 경로를 구해줍니다. 이후 둘의 이동 경로가 부딪히거나 크로스로 건너가는지 확인해줍니다.
우의 경우를 통과한 여러 이동 경로 중 가장 짧은 이동 경로를 출력해주면 됩니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

#define INF 100000000

vector<vector<int>> RedMaze, BlueMaze;
deque<pair<int, int>> RedRoute, BlueRoute;
pair<int, int> RedStart, RedEnd, BlueStart, BlueEnd;

int MinRouteCount = INF;
int RedCount;

void CheckEnableRoute()
{
    deque<pair<int, int>> rRoute = RedRoute;
    deque<pair<int, int>> bRoute = BlueRoute;
    pair<int, int> red, blue, prevRed, prevBlue;
    
    int count = rRoute.size() > bRoute.size() ? rRoute.size() : bRoute.size();
    
    red = RedStart;
    blue = BlueStart;
        
    while(!rRoute.empty() || !bRoute.empty())
    {
        if(!rRoute.empty())
        {
            prevRed = red;
            red = rRoute.front();
            rRoute.pop_front();
        }
        
        if(!bRoute.empty())
        {
            prevBlue = blue;
            blue = bRoute.front();
            bRoute.pop_front();
        }
        
        //지나갈 수 없는 경우 체크
        if(red.first == blue.first && red.second == blue.second ||
           prevRed.first == blue.first && prevRed.second == blue.second && red.first == prevBlue.first && red.second == prevBlue.second)
        {
            return;
        }
    }
    
    if(MinRouteCount > count)
    {
        MinRouteCount = count;
    }
}

void FindBlueRoute(int x, int y, int count)
{
    if(x == BlueEnd.first && y == BlueEnd.second)
    {
        BlueRoute.push_back({x, y});
        CheckEnableRoute();
        BlueRoute.pop_back();
        
        return;
    }
        
    int dirX[4] = {1, -1, 0, 0};
    int dirY[4] = {0, 0, 1, -1};
    
    BlueMaze[x][y] = count;
    
    for(int i = 0; i < 4; i++)
    {
        if(x + dirX[i] < 0 || x + dirX[i] >= BlueMaze.size() || y + dirY[i]< 0 || y + dirY[i] >= BlueMaze[0].size())
            continue;
        
        //두 개의 수레가 겹치는 경우
        if(BlueMaze[x + dirX[i]][y + dirY[i]] == 0)
        {
            BlueRoute.push_back({x + dirX[i], y + dirY[i]});
            FindBlueRoute(x + dirX[i], y + dirY[i], count+1);
            BlueRoute.pop_back();
        }
    }
    
    BlueMaze[x][y] = 0;
}

void FindRedRoute(int x, int y, int count)
{
    if(x == RedEnd.first && y == RedEnd.second)
    {
        RedRoute.push_back({x, y});
        FindBlueRoute(BlueStart.first, BlueStart.second, 1);
        RedRoute.pop_back();
        
        return;
    }
        
    int dirX[4] = {1, -1, 0, 0};
    int dirY[4] = {0, 0, 1, -1};
    
    RedMaze[x][y] = count;
    
    for(int i = 0; i < 4; i++)
    {
        if(x + dirX[i] < 0 || x + dirX[i] >= RedMaze.size() || y + dirY[i] < 0 || y + dirY[i] >= RedMaze[0].size())
            continue;
        
        if(RedMaze[x + dirX[i]][y + dirY[i]] == 0)
        {
            RedRoute.push_back({x + dirX[i], y + dirY[i]});
            FindRedRoute(x + dirX[i], y + dirY[i], count+1);
            RedRoute.pop_back();
        }
    }
    
    RedMaze[x][y] = 0;
}

int solution(vector<vector<int>> maze) {
    int answer = 0;
    RedCount = 0;
    
    RedMaze.assign(maze.size(), vector<int>(maze[0].size(), 0));
    BlueMaze.assign(maze.size(), vector<int>(maze[0].size(), 0));
    
    //시작 지점, 도착 지점, 벽 탐색
    for(int i = 0; i < maze.size(); i++)
    {
        for(int j = 0; j < maze[0].size(); j++)
        {
            if(maze[i][j] == 1)
            {
                RedStart = {i, j};
            }else if(maze[i][j] == 3)
            {
                RedEnd = {i, j};
            }else if(maze[i][j] == 2)
            {
                BlueStart = {i, j};
            }else if(maze[i][j] == 4)
            {
                BlueEnd = {i, j};
            }else if(maze[i][j] == 5)
            {
                RedMaze[i][j] = -1;
                BlueMaze[i][j] = -1;
            }
        }
    }
    
    FindRedRoute(RedStart.first, RedStart.second, 1);
    
    if(MinRouteCount != INF)
    {
        answer = MinRouteCount-1;
    }
    
    return answer;
}

출저

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