[프로그래머스/C++] PCCP 기출문제 4번

 

 

문제

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

 

[문제 설명]

 

n * m 의 격자판이 주어지고 빨간 수레와, 파란 수레가 주어진다. 그리고 빨간 수레와 파란수레가 각자 목표로 하는 지점까지 도착하는데 걸리는 최소 턴수를 구하는 문제이다.

 

이때, 빨간수레는 1, 파란수레는 2, 빨간 수레의 도착점은 3, 파란 수레의 도착점은 4이고, 벽은 5로 주어진다. 이동할 위치에 다른 수레가 있으면 이동할 수 없으며, 서로 위치를 교환 할 수도 없다. 또한 이미 지나왔던 길은 다시 갈 수 없다.

 

 

 

풀이

 

[풀이]

 

먼저 문제를 읽고 어떻게 풀면 좋을지 고민했는데, 다행히 미로의 크기가 크지 않았기 때문에 완전 탐색을 해도 시간이 충분하겠다는 생각이 들었다. 그래서 완전 탐색으로 코드를 짰다.

​

그리고 경우의 수를 나누었다. 파란 수레가 먼저 움직일 수도 있고, 빨간 수레가 먼저 움직일 수도 있으므로, 두 경우를 다 구했다.

 

만약 파란 수레나 빨간 수레가 도착점에 도달했다면, 파란수레는 이동하지 않으므로 파란수레의 턴을 넘기도록 코드를 짰다.

문제가 어렵지는 않았지만 구현하는데 좀 시간이 걸렸다.

 

 

Code

 

 

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

using namespace std;
// 미로 크기가 작으므로 완전 탐색, 빨강이 먼저 이동하는 경우, 파랑이 먼저 이동하는 경우
vector<vector<bool>> visitedBlue;
vector<vector<bool>> visitedRed;
vector<vector<int>> realMaze;
int mazeY;
int mazeX;
int taRy,taRx, taBy,taBx;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int answer = 40;
int moveFunction(int targetColor,int ry,int rx, int by, int bx, bool doneR, bool doneB, int turnCnt)
{
    int mY;
    int mX;
    turnCnt+=1;
    if (doneR&&doneB)
    {
        // 끝
        if (answer>turnCnt/2)
        {
            answer=turnCnt/2;
        }
        return 1;
    }    
    else if (targetColor==3&&doneR)
    {
        // 바로 다음으로
        moveFunction(4, ry, rx, by, bx, doneR, doneB,turnCnt);
        return 0;
    }
    else if (targetColor==4&&doneB)
    {
        // 바로 다음으로
         moveFunction(3, ry, rx, by, bx, doneR, doneB,turnCnt);
        return 0;
    }
    else
    {
        for (int i=0; i<4; i++)
        {
            if (targetColor==3)
            {
                mY=ry+dy[i];
                mX=rx+dx[i];
            }
            else
            {
                mY=by+dy[i];
                mX=bx+dx[i];
            }
            if (0<=mY&&mY<mazeY && 0<=mX&&mX<mazeX)
            {
                if (realMaze[mY][mX]!=5 &&realMaze[mY][mX]!=1&&realMaze[mY][mX]!=2) //벽도 아니고 파랑 빨강수레가 없다면
                {
                    if (targetColor==3) //빨간 수레라면, 이동시키고 파란 수레를 다음에 이동
                    {
                        if (!visitedRed[mY][mX])
                        {
                            realMaze[ry][rx]=0;
                            visitedRed[mY][mX]=true;
                            realMaze[mY][mX]=1;
                            if (mY== taRy && mX == taRx)
                            {
                                moveFunction(4, mY, mX, by, bx,true, doneB,turnCnt);
                            }
                            else
                            {
                                moveFunction(4, mY, mX, by, bx,doneR,doneB,turnCnt);
                            }
                            realMaze[mY][mX]=0; 
                            realMaze[ry][rx]=1;
                            visitedRed[mY][mX]=false;
                        }
                    }
                    else // 파란수레의 경우
                    {
                        if (!visitedBlue[mY][mX])
                        {
                            realMaze[by][bx]=0;
                            visitedBlue[mY][mX]=true;
                            realMaze[mY][mX]=2;
                            if (mY== taBy && mX == taBx)
                            {
                                moveFunction(3, ry, rx, mY, mX, doneR, true,turnCnt);
                            }
                            else
                            {
                                moveFunction(3, ry, rx, mY, mX,doneR,doneB,turnCnt);
                            }
                            realMaze[mY][mX]=0; 
                            realMaze[by][bx]=2;
                            visitedBlue[mY][mX]=false;
                        }
                    }
                }
            }
        }
    }
    return 0;
}


int solution(vector<vector<int>> maze) {
    mazeY=maze.size();
    mazeX=maze[0].size();
    vector<bool> a(mazeX,false);
    int stRy,stRx, stBy,stBx;
    for (int i =0; i<mazeY; i++)
    {
        realMaze.push_back(maze[i]);
        visitedBlue.push_back(a);
        visitedRed.push_back(a);
        for (int j =0; j<mazeX; j++)
        {
            if (maze[i][j]==1)
            {
                stRy=i;
                stRx=j;
            }
            else if (maze[i][j]==2)
            {
                stBy=i;
                stBx=j;
            }
            else if (maze[i][j]==3)
            {
                taRy=i;
                taRx=j;
            }
            else if (maze[i][j]==4)
            {
                taBy=i;
                taBx=j;
            }
        }
    }    
    visitedRed[stRy][stRx]=true;
    visitedBlue[stBy][stBx]=true;
    moveFunction(3,stRy, stRx, stBy, stBx, false, false,0);
    moveFunction(4,stRy, stRx, stBy, stBx, false, false,0);
    if (answer==40)
    {
        return 0;
    }
    return answer;
}

 

---

 

코드가 좀 긴데, 말 그대로 구현하느라 길이가 길어져서 그렇다.

 

C++에서 초기화가 헷갈리는 것 같다;; 

C++ STL 사용법을 좀 더 익히는 연습을 하자...

 

프로그래머스