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

---

🔗 문제 링크

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

프로그래머스

---

728x90

👩‍💻 코드

#include <vector>
#include <queue>
#include <utility>
#include <iostream>

using namespace std;

int solution(vector<vector<int>> maps) {
    vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    queue<pair<int, int>> q;
    int n = maps.size();
    int m = maps[0].size();
    int answer = 1;
    
    q.push({0, 0});
    maps[0][0] = -1;
    
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            auto [x, y] = q.front();
            q.pop();
            
            if (x == n - 1 && y == m - 1) {
                return answer;
            }
            
            for (auto [dx, dy] : directions) {
                int newX = x + dx;
                int newY = y + dy;
                
                if (newX >= 0 && newX < n && newY >= 0 && newY < m && maps[newX][newY] == 1) {
                    q.push({newX, newY});
                    maps[newX][newY] = -1;
                }
            }
        }
        answer++;
    }
    
    return -1;
}

---

📝 풀이

방향을 정의하고 n과 m값을 초기화합니다.

시작 위치를 큐에 삽입하고 maps에 방문했다는 의미로 값을 -1로 수정합니다.

 

큐에서 현재 위치를 꺼내고 목표 위치인지 확인합니다.

목표 위치인 경우 answer을 return하고 그렇지 않다면 다음 경로를 탐색합니다.

아까 정의한 네 방향 중 이동 가능한 위치를 확인하고 큐에 추가합니다.

 

탐색이 끝나면 answer를 증가시킵니다.

경로가 없는 경우에는 -1을 return 합니다.