[프로그래머스] - 게임 맵 최단거리(C++)

프로그래머스

[문제 설명]

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

• 첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.

• 두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.

위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.

만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

제한사항

• maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
  • n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
• maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
• 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

---

 

maps	answer
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]	11
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]	-1

입출력 예 설명

입출력 예 #1주어진 데이터는 다음과 같습니다.

캐릭터가 적 팀의 진영까지 이동하는 가장 빠른 길은 다음 그림과 같습니다.

따라서 총 11칸을 캐릭터가 지나갔으므로 11을 return 하면 됩니다.

입출력 예 #2문제의 예시와 같으며, 상대 팀 진영에 도달할 방법이 없습니다. 따라서 -1을 return 합니다.

---

[문제 풀이]

생각한대로 코드에 옮겨적었는데 운이 좋게 맞았다.

이것과 비슷한 문제가 있었던것 같다. 백준의 로봇청소기였던가..

이렇게 이동하는 게임같은 문제는 다음에 이동할수 있는 위치를 아래 코드에서 처럼 배열에 저장해놓으면 편하게 풀수있다.

이 문제는 최단거리를 구하는 문제이므로 BFS로 접근했다.

시작 위치(0,0)와 도착할 위치(n,m)는 정해져있다.

문제의 핵심 로직은 아래와 같다.

1. 초기 위치를 큐에 넣는다.
2. 큐의 front 값을 확인하여 목표 위치와 같다면 map의 현재 위치에 있는 값을 return
3. 같지 않다면 pop하여 맨 앞의 값을 빼주고, for문을 통해 이동할 수 있는 위치를 탐색하여 큐에 넣어준다.
4. queue가 empty가 아닐때까지 2번부터 반복

map[x][y]가 1일때만 움직일수 있는 위치로 파악하여 이 전 위치에 저장된 값을 더하면서 이동하면 된다.

그러면 여태까지 이동한 count와 이동할수있는 위치를 동시에 확인할수있다.

파이팅 !

코드가 깨끗하고 명확하게 보일진 모르겠지만, 누군가에게 도움이 될 수도.. 있기에..

더보기

#include<vector>
#include<utility>
#include<queue>
using namespace std;

int solution(vector<vector<int> > maps)
{
    int answer = 0;

    int n = maps.size();
    int m = maps[0].size();
    if( n == 1 && m == 1) return 0;

    vector<int> wayX = {-1,1,0,0};  //  left, right, up, down
    vector<int> wayY = {0,0,-1,1};  //  left, right, up, down
    pair<int,int> cur_pos = {0,0};

    queue<pair<int,int>> q;
    q.push(cur_pos);

    while(!q.empty())
    {
        cur_pos = q.front();
        if(cur_pos.first == n-1 && cur_pos.second == m-1)
        {
            return maps[cur_pos.first][cur_pos.second];
        }
        q.pop();

        for(int i =0; i < 4; i++)
        {
            int dx = cur_pos.first + wayX[i];
            int dy = cur_pos.second + wayY[i];

            if(dx >= 0 && dy >= 0 && dx < n && dy < m && maps[dx][dy] == 1)
            {
                q.push({dx,dy});
                maps[dx][dy] += maps[cur_pos.first][cur_pos.second];
            }
        }
    }

    return -1;
}