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

< 해설 >

처음으로 풀어보는 BFS 문제이다. DFS는 트리나 여러가지 탐색문제에도 많이 사용해봐서 알고 있었는데 BFS는 처음 풀어봄..!

처음에는 그냥 동일하게 재귀로 풀면 되지 않을까? 라고 생각했는데 재귀로 푸니 시간에서 걸리는 문제들이 생긴다. (정확성도 틀린것도 있음 ㅠㅠ) 

 

BFS는 가장 빠르게 도착하는 값만 return 하면 된다. 재귀와는 다르게 일을 큐에 한개씩 넣어줬을때 조건을 완료하는 값이 있다면 그 값이 가장 빠르게 도착하는 값이다. (전체 다 탐색할 이유x)

그래서 순서대로 일을 큐에 넣어준다. 찾아보니 가중치라는 개념도 있다고 하는데 상하좌우 모두 동일하게 넣어주면 되어서 여기에는 가중치가 필요하진 않다고 함. (가중치가 필요한 작업은 cost가 존재하는 때 인듯합니다.)

 

현재 x,y 좌표에서 상하좌우로 1칸씩 이동된 좌표가 이동할 수 있는 맵이라면 그 좌표에 원점으로부터 얼마나 이동했는지를 넣어준다. 이렇게 얼마나 이동했는지도 알 수 있다! 

만약 큐가 비었고 모든 타일에 대한 탐색이 끝났는데도 목적지에 도착하지 않으면 -1을 리턴함으로써 목적지에 도착할 수 없다고 알려준다.

 

 

< 문제 >

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

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

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.

아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

 

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

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

위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다. 만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.

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

 

 

< 풀이 >

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

int map_count[101][101];
int depense[4][2] = { {0,1}, {1,0}, {-1, 0}, {0, -1} };

int solution(vector<vector<int> > maps)
{
    queue<pair<int, int>> task; 
    memset(map_count, -1, sizeof(map_count));
    
    task.push({0,0});
    map_count[0][0] = 1;
    
    while(!task.empty())
    {
        int y = task.front().first;
        int x = task.front().second;
        task.pop();
        
        // 종료조건
        if(y == maps.size()-1 && x == maps[0].size()-1)
            return map_count[y][x];
        
        // 상 하 좌 우 탐색
        for(int i=0; i<4; i++)
        {
            int newX = x + depense[i][1];
            int newY = y + depense[i][0];
            
            if(newX < maps[0].size() && 0 <= newX
               && newY < maps.size() && 0 <= newY)
            {
                if(maps[newY][newX] == 1 && map_count[newY][newX] == -1 )
                {
                    // task 에 일 넣어주기 가능.
                    map_count[newY][newX] = map_count[y][x] +1;
                    task.push({newY, newX});
                }
            }
        }
    }
    
    
    return -1;
}