[C++] Programmers Lv. 2 "게임 맵 최단거리"

🔵 문제 링크

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

프로그래머스

 

🔵 문제 풀이

아주 기초적인 bfs 문제로, bfs의 특성을 활용하여 목적지까지 최단 거리를 찾는 문제이다.

주의해야 할 점은 n과 m이 서로 다를 수도 있으므로 행과 열을 헷갈리지 않는 것이다.

 

🔵 전체 코드

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

// 그냥 bfs 문제
// n과 m은 다르다. (행, 열 헷갈리지 않게 주의)
int solution(vector<vector<int>> maps)
{
    const int ROW = maps.size();  // 행 (세로)
    const int COL = maps[0].size();

    int dx[4] = { 1, -1, 0, 0 };
    int dy[4] = { 0, 0, 1, -1 };

    vector<vector<int>> visited(ROW, vector<int>(COL, -1));
    queue<pair<int, int>> q;

    q.push({ 0, 0 });
    visited[0][0] = 1;

    while (!q.empty())
    {
        int r = q.front().first;
        int c = q.front().second;
        q.pop();

        if (r == ROW - 1 && c == COL - 1)
            return visited[r][c];

        for (int i = 0; i < 4; i++)
        {
            int nr = r + dx[i];
            int nc = c + dy[i];

            if (nr < 0 || nc < 0 || nr >= ROW || nc >= COL) continue;
            if (maps[nr][nc] == 0 || visited[nr][nc] != -1) continue;

            q.push({ nr, nc });
            visited[nr][nc] = visited[r][c] + 1;
        }
    }

    return -1;
}

 

🔵 시간 복잡도

maps의 크기를 n * m이라 할 때, bfs는 모든 노드를 한 번씩 확인하므로 최종 시간 복잡도는 O(N * M)이다.