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

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

 

해설

 

map이 있을 때, (0, 0)에서 (n-1, m-1) 까지의 최단 거리를 구하는 문제이다. 

BFS를 이용하여 탐색가능한 좌표를 따라 이동하고 최단거리를 구해보자.

 

먼저, 큐에 출발 위치 (0,0)을 삽입하고, dist[0][0]을 0으로 초기화 한다.

dist[i][j]는 (0, 0)에서 (i, j)까지의 최단거리를 기록하는 배열로, 좌표를 방문하지 않은 경우 -1로 초기화되어있다.

 

이후, 큐에서 좌표를 하나씩 꺼내면서 이동가능한 좌표를 확인하고 새로운 좌표를 큐에 넣는다.

이동가능한 좌표는 현재 좌표의 동서남북에 있는 좌표 중, (0, 0) ~ (n-1, m-1) 내에 있고, 아직 방문한 적이 없으며, maps[i][j] 값이 1인 좌표이다.

새로운 좌표를 큐에 넣을 때는 (0, 0)에서 새로운 좌표까지의 거리를 계산해야 하는데, 새로운 좌표까지의 거리는 현재 좌표까지의 거리+1이 된다.

 

최종적으로 dist[n-1][m-1]이 -1이라면 (n-1, m-1)까지 도달하지 못한다는 의미이므로 -1을 리턴한다.

도달 가능한 경우, dist[n-1][m-1]+1(처음칸 포함) 을 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cctype>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

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

int solution(vector<vector<int>> maps) {
    
    int n = maps.size();
    int m = maps[0].size();
    
    queue<ii> q;
    q.push({0, 0});
    
    int dist[100][100];
    for (int i=0; i<100; i++) {
        for (int j=0; j<100; j++) dist[i][j] = -1;
    }
    dist[0][0] = 0;
    
    while (!q.empty()) {
        
        ii cur = q.front();
        q.pop();
        
        for (int i=0; i<4; i++) {
            int nx = cur.X+dx[i];
            int ny = cur.Y+dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (dist[nx][ny] != -1 || !maps[nx][ny]) continue;
            q.push({nx, ny});
            dist[nx][ny] = dist[cur.X][cur.Y]+1;
        }
    }
    
    if (dist[n-1][m-1] == -1) return -1;
    return dist[n-1][m-1]+1;
}