게임 맵 최단거리 - Level 4

해결방법

문제는 (0,0)부터 (n-1, m-1)까지 가는 거리 중 최소값을 구하는 것이다. 이런 문제는 항상 BFS가 답이다! DFS로 구현해도 되지만 DFS의 TimeComplexity가 너무 크기 때문에 시간초과가 된다. 다익스크라 알고리즘도 BFS를 쓰는 이유로 사용되고 있다! 삼성에서 이런 문제가 출제되기도 하는데 무조건 BFS다!
나는 struct로 (y,x)위치와 거리가 있는 구조체를 만들었다.

 struct node {
    int y, x, d;
    node(int yy, int xx, int dd) : y(yy), x(xx), d(dd) {}
    node() {}
};

그 다음 BFS로 구현하였고 먼저 (n - 1, m - 1)도착한 거리를 answer에 대입하고 break해주었다. BFS는 먼저 도착한 것이 무조건 짧기 떄문이다.

    while(!q.empty()) {
        node here = q.front();
        q.pop();
        if(here.y == h - 1 && here.x == w - 1) {
            answer = here.d;
            break;
        }
        for(int i = 0; i < 4; ++i) {
            int nextx = here.x + dx[i];
            int nexty = here.y + dy[i];
            if(nextx < 0 || nextx >= w || nexty < 0 || nexty >= h || maps[nexty][nextx] == 0) continue;
            if(v[nexty][nextx]) continue;
            v[nexty][nextx] = true;
            q.push(node(nexty,nextx, here.d+1));
        }
    }

전체코드

#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int dy[] = {1,-1,0,0};
int dx[] = {0,0,1,-1};
struct node {
    int y, x, d;
    node(int yy, int xx, int dd) : y(yy), x(xx), d(dd) {}
    node() {}
};
int solution(vector<vector<int> > maps)
{
    int answer = -1;
    int h = maps.size();
    int w = maps[0].size();
    vector<vector<bool>> v(h+1, vector<bool>(w+1, false));
    queue<node> q;
    q.push(node(0,0,1));
    v[0][0] = true;
    while(!q.empty()) {
        node here = q.front();
        q.pop();
        if(here.y == h - 1 && here.x == w - 1) {
            answer = here.d;
            break;
        }
        for(int i = 0; i < 4; ++i) {
            int nextx = here.x + dx[i];
            int nexty = here.y + dy[i];
            if(nextx < 0 || nextx >= w || nexty < 0 || nexty >= h || maps[nexty][nextx] == 0) continue;
            if(v[nexty][nextx]) continue;
            v[nexty][nextx] = true;
            q.push(node(nexty,nextx, here.d+1));
        }
    }
    if(answer == 201)
        answer = -1;
    return answer;
}

[출처] https://programmers.co.kr/learn/courses/30/lessons/1844