프로그래머스, C++) Lv 2. 게임 맵 최단거리

DFS로는 최단 거리를 구할 수 없음

BFS로 가능 + 상하좌우 라는 방향을 추가

#include <bits/stdc++.h>
using namespace std;

int solution(vector<vector<int>> maps) {
    int n = maps.size();
    int m = maps[0].size();

    vector<vector<int>> dist(n, vector<int>(m, 0));   // 0: 미방문, 그 외: 거리
    queue<pair<int,int>> q;

    // 이동 방향(상, 하, 좌, 우)
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    // 시작점 (0,0) 이 1(통로)인지 확인
    if (maps[0][0] == 0) return -1;

    // 시작 설정
    dist[0][0] = 1;
    q.push({0, 0});

    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();

        // 목표 도달 시 바로 반환(최초 도달 = 최단거리)
        if (x == n-1 && y == m-1) return dist[x][y];

        for (int k = 0; k < 4; ++k) 
        {
            int nx = x + dx[k];
            int ny = y + dy[k];

            // 1) 범위 내, 2) 벽이 아님(=1), 3) 미방문(dist==0)
            if (nx >= 0 && nx < n && ny >= 0 && ny < m
                && maps[nx][ny] == 1 && dist[nx][ny] == 0) {

                dist[nx][ny] = dist[x][y] + 1; // 거리 갱신
                q.push({nx, ny});
            }
        }
    }

    // 도달 불가
    return -1;
}