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

문제

---

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

풀이

---

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return하는 문제이다. 캐릭터의 이동을 구현하고 bfs를 통해 최소 이동 횟수를 구한다.

#include<vector>
#include <queue>

using namespace std;

#define MAX 101

vector<vector<int>> bfs_map;
int answer = -1;

int isVisit[MAX][MAX];
int row, col;
int dist[MAX][MAX];

int x_dir[4] = { -1,1,0,0 };
int y_dir[4] = { 0,0,-1,1 };

queue <pair<int, int>> que;

void bfs(int x_cur, int y_cur)
{
    isVisit[x_cur][y_cur] = true;
    que.push(make_pair(x_cur, y_cur));
    dist[x_cur][y_cur]++;

    while (!que.empty())
    {
        int x = que.front().first;
        int y = que.front().second;

        que.pop();

        for (int i = 0; i < 4; ++i)
        {
            int x_new = x + x_dir[i];
            int y_new = y + y_dir[i];

            if ((x_new >= 0 && x_new < row) && (y_new >= 0 && y_new < col) && isVisit[x_new][y_new] == false && bfs_map[x_new][y_new] == 1)
            {
                isVisit[x_new][y_new] = true;
                que.push(make_pair(x_new, y_new));
                dist[x_new][y_new] = dist[x][y] + 1;
                
            }
        }
    }

    if (isVisit[row - 1][col - 1] == false)
    {
        answer = -1;
    }

    else
    {
        answer = dist[row - 1][col - 1];
    }

}

int solution(vector<vector<int>> maps)
{
    bfs_map = maps;

    row = maps.size();
    col = maps[0].size();
    bfs(0,0);


    return answer;
}