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

문제 링크

 

풀이법

큐를 이용해서 풀 수 있습니다. 이 문제는 깊이 우선이 아니라 너비 우선 방식으로 풀어야 합니다. 너비 우선 방식을 이용하면 모든 노드에 도달하는 카운트가 최소가 됩니다. 현재 노드에서 동서남북 방향을 훑어 보고 처음 방문한 곳이면서 노드 값이 1인 경우에 탐색을 합니다. 이 과정이 순차적으로 이루어지며, 탐색을 선점하게 되면 해당 위치의 카운트는 갱신되지 않게 코드를 작성할 것이기 때문입니다.

 

프로그래머스에선 이차원 배열을 vector로 선언했을 때 속도가 더 빠르게 나오는 걸 확인했습니다. 하지만 효율성 테스트와 비주얼 스튜디오 2019에선 당연히 정적으로 선언한 경우가 더 빨랐습니다. 예제 1번 기준으로는 0.2ms 차이가 났고, 효율성 테스트에서는 0.05~0.07ms로 작은 차이긴 합니다.

 

아래 코드에서 유심히 봐야 할 것은 큐에 다음 노드를 넣어주는 시점에 방문한 걸로 처리해야 한다는 점입니다. 그렇지 않으면 여러 노드가 중복 삽입되기 때문에 효율성 테스트에서 실패합니다.

 

코드

int solution(vector<vector<int> > maps)
{
    const int height = maps.size();
    const int width = maps[0].size();
    vector<vector<int>> answer(height, vector<int>(width));
    vector<vector<bool>> visited(height, vector<bool>(width));
    //int answer[100][100] = {0};
    //bool visited[100][100] = {false};
    int w_dir[4] = { 0, 1, 0, -1 };
    int h_dir[4] = { 1, 0, -1, 0 };
    answer[0][0] = 1;
    queue<pair<int, int>> q;

    q.push({ 0, 0 });
    while (!q.empty())
    {
        auto [cur_x, cur_y] = q.front();
        q.pop();
        //visited[cur_y][cur_x] = true;
        for (int i = 0; i < 4; ++i)
        {
            auto ww = cur_x + w_dir[i];
            auto hh = cur_y + h_dir[i];
            if (ww < 0 || ww >= width || hh < 0 || hh >= height) continue;

            if (false == visited[hh][ww] && maps[hh][ww])
            {
                answer[hh][ww] = answer[cur_y][cur_x] + 1;
                visited[hh][ww] = true;
                q.push({ ww, hh });
            }
        }
    }
    if (!visited[height - 1][width - 1]) return -1;
    else return answer[height - 1][width - 1];
}