게임 맵 최단거리(15분)

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

구현 아이디어 51초 구현 14분

풀이

최단 거리 문제를 한번만 접해봤으면 쉽게 풀 수 있는 문제이다.(그래도 이제 이런 말을 하다니 기분이 너무 좋다!) BFS를 이용해 풀었다.

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

int ch[101][101];

struct Data
{
    int r;
    int c;
    int sum;
    Data(int r, int c, int sum)
    {
        this->r = r;
        this->c = c;
        this->sum = sum;
    }
};

// 구현 아이디어 51초. 채점 시간 14분 28초.
int solution(vector<vector<int> > maps)
{
    int answer = 0;
    
    // 최단 거리. BFS.
    queue<Data> Q;
    ch[0][0] = 1;
    Q.push(Data(0, 0, 1));
    
    // 12, 3, 6, 9.
    int dr[4] = {-1, 0, 1, 0};
    int dc[4] = {0, 1, 0, -1};
    
    int N = maps.size();
    int M = maps[0].size();
    
    while(!Q.empty())
    {
        Data b = Q.front();
        Q.pop();
        
        if(b.r == N - 1 && b.c == M - 1)
        {
            answer = b.sum;
            break;
        }
        
        for(int i = 0; i < 4; ++i)
        {
            int rr = b.r + dr[i];
            int cc = b.c + dc[i];
            
            if(rr < 0 || cc < 0 || rr >= N || cc >= M) continue;
            if(ch[rr][cc] == 0 && maps[rr][cc] != 0)
            {
                ch[rr][cc] = 1;
                Q.push(Data(rr, cc, b.sum + 1));
            }
        }
    }
    
    if(answer == 0) answer = -1;
    
    return answer;
}