[2023년 11월 24일]게임 맵 최단거리(7분)

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

구현 아이디어 0분 구현 7분

풀이

무난한 문제라 구현 아이디어 0분, 글만 읽고 풀었다.

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

int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

// 최단 거리. BFS.
struct Data
{
    int r, c, sum;
    Data(int r, int c, int sum)
    {
        this->r = r;
        this->c = c;
        this->sum = sum;
    }
};

int solution(vector<vector<int> > maps)
{
    int answer = 0;
    int n = maps.size();
    int m = maps[0].size();
    
    queue<Data> Q;
    Q.push(Data(0, 0, 1));
    maps[0][0] = 0;
    
    bool end = false;
    while(!Q.empty())
    {
        Data data = Q.front();
        Q.pop();
        
        if(data.r == n - 1 && data.c == m - 1)
        {
            answer = data.sum;
            end = true;
            break;
        }
        
        for(int i = 0; i < 4; ++i)
        {
            int check_r = data.r + dr[i];
            int check_c = data.c + dc[i];
            
            if(check_r < 0 || check_c < 0 || check_r >= n || check_c >= m || !maps[check_r][check_c])
                continue;
            
            Q.push(Data(check_r, check_c, data.sum + 1));
            
            // 여기서 0으로 갱신하지 않으면 시간 초과가 난다.
            // 여기서 0 갱신 해야 front들이 상, 하, 좌, 우를 검색할 때 큐에 원소를 덜 넣게 된다.
            maps[check_r][check_c] = 0;
        }
    }
    
    if(!end) answer = -1;
    
    return answer;
}