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

 

이번에 티스토리에서도 오블완 챌린지를 한다고 한다!

 

항상 문제를 풀고 블로그에 올리지 못하는 것이 아쉬웠는데, 앞으로 21일간 문제 풀이 올리는 오블완 챌린지를 도전 해보겠다!

 

ps. 알고 초급자임

---

🔗 문제 링크

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

프로그래머스

 

 

✍🏻 문제 설명

2차원 배열 형태의 지도에서 시작점에서 끝점까지의 최단 경로를 찾는 문제이다. 각 칸은 이동 가능한 길(1)과 벽(0)으로 표시되며, 상하좌우로만 이동할 수 있다. 시작점에서 끝점까지 도달할 수 있는 최소한의 이동 횟수를 구하며, 도달이 불가능한 경우 -1을 반환하면 된다.

이런 판이 있다면?

목적지까지의 최단 거리를 찾는 것!

💁🏻‍♀️ 내 풀이

우선 문제를 보고 최단거리 문제니 BFS 또는 DFS를 쓰는 문제인 것은 캐치! 결과적으로 이 문제는 BFS를 사용한다. 출발점에서 도착점까지의 최단 경로만 필요하고, 도달할 수 있는 최단 거리만 찾으면 되기 때문이다. 즉 모두 탐색할 필요가 없기 때문에 BFS 사용하면 된다.

 

그리고 BFS니 큐를 사용해서 처리 하면 된다. 

 

구현의 기본 흐름:

1. 시작점(0, 0)부터 탐색을 시작하여 큐에 삽입
2. 큐에서 좌표를 하나씩 꺼내 상하좌우로 이동 가능한 칸을 확인
3. 이동 가능한 칸이 있다면 해당 칸까지의 거리를 기록하고 큐에 넣기
4. 목표 지점에 도달했으면 탐색을 종료하고 거리 값을 반환

 

🤖 코드

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

int BFS(vector<vector<int>> maps) {
    int directions[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
    queue<pair<int, int>> q;
    int rows = maps.size();
    int cols = maps[0].size();
    
    q.push({0, 0});
    
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        int current_distance = maps[x][y];
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int new_x = x + directions[i][0];
            int new_y = y + directions[i][1];
            
            if (new_x < 0 || new_x >= rows || new_y < 0 || new_y >= cols) continue;
            if (new_x == rows - 1 && new_y == cols - 1) return current_distance + 1;

            if (maps[new_x][new_y] == 1) {
                maps[new_x][new_y] = current_distance + 1;
                q.push({new_x, new_y});
            }
        }
    }
    return -1;
}

int solution(vector<vector<int>> maps) {
    return BFS(maps);
}