[C++로 풀이] 게임 맵 최단거리 (BFS)⭐⭐

Date: 2021.03.04 Updated: 2021.03.04

카테고리: Programmers

태그: Coding Test Algorithm

📌 게임 맵 최단거리

난이도 ⭐⭐

🚀 문제

🚀 내 풀이

🔥 첫 번째 풀이 ⭕

BFS 사용한 이유
- 가중치가 없다.
- BFS를 사용하면 출발지로부터 각 노드까지의 방문은 최단 경로로 이루어질 수 밖에 없다.
  - 큐를 사용하여 “너비 우선 탐색”을 하기 때문에 자연스럽게 출발지로부터 거리 순으로 방문이 되기 때문이다.
  - 그리고 도착지가 되는 노드의 최단 경로만 답으로 도출하면 된다.
    - 처음엔 도착지가 되는 노드의 최단 경로 딱 하나만 구하면 되나 싶었는데, 사실 도착지 노드의 최단 경로는 곧 다른 노드들로부터의 최단 경로에서 구해지는거라 어차피 다른 노드들의 최단 경로도 필요 하다.

도착지 노드 하나가 확실해서 처음엔 A* 알고리즘을 생각했었다. 근데 A* 알고리즘을 적용해보기엔 휴리스틱을 어떻게 해야할지 까다로웠다. 그냥 가중치도 없겠다, 모든 노드를 탐색하겠다는 생각으로 BFS 를 선택하였다. 그리고 다행히도 효율성 테스트에도 통과했다. 깊이 우선 탐색이 아닌 너비 우선 탐색이기에 되돌아 오는 과정이 없어서 모든 노드를 탐색하더라도 O(m * n) 시간 복잡도를 넘지 않을 것 같다.

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

struct Pos {
    int x;
    int y;
    Pos(int _y, int _x) { y = _y; x = _x; }
};

int solution(vector<vector<int> > maps)
{
    const int n = maps.size(); // n 행
    const int m = maps[0].size(); // m 열
    // 방향 (시계방향으로 설정했다. 상우하좌. 방향 순서에 따라 노드의 방문 순서가 달라질 수 있다. 일반 큐라 큐에 들어간 순서대로 나오기 때문)
    int deltaY[4] = { -1, 0, 1, 0 }; 
    int deltaX[4] = { 0, 1, 0, -1 };

    vector<vector<bool>> checked(n, vector<bool>(m)); // 예약 된 적이 있는지. 큐에 삽입된적이 있는 위치일 때 true, 즉 이미 출발지로부터의 최단 거리가 업뎃 되어있는 
    vector<vector<int>> dist(n, vector<int>(m)); // 출발지로부터 해당 위치까지의 최단 거리
    queue<Pos> q; // 큐

    /* 출발지는 예약 작업을 할 수 없고 바로 방문해야 하니 미리 작업 */
    q.push(Pos(0, 0));  // 큐에 넣기
    checked[0][0] = true; // 예약
    dist[0][0] = 1; // 출발지의 거리는 1

    while (!q.empty()) {
        /* 방문 */
        Pos pos = q.front();
        q.pop();
        int nowY = pos.y;
        int nowX = pos.x;

        /* 예약 */
        for (int i = 0; i < 4; ++i) {  // 방문한 곳을 기준으로 상우하좌 4가지 방향에 있는 곳들 예약 처리
            int nextY = nowY + deltaY[i];
            int nextX = nowX + deltaX[i];

            /* 다음에 방문할 수 잇는지, 즉 예약할 수 있는지 체크 */
            if (nextY < 0 || nextY >= n || nextX < 0 || nextX >= m) // 1. 맵을 벗어난다면 예약할 수 없는 방향
                continue;
            if (maps[nextY][nextX] == 0) // 2. 벽이라면 예약할 수 없는 방향
                continue;
            if (checked[nextY][nextX]) // 3. 이미 예약된적이 있다면 예약할 수 없는 방향
                continue;
            
            /* 다음에 방문할 수 있는 곳이니 큐에 넣어 예약하기! -> ⭐그와 동시에 최단거리 업데이트⭐ */
            q.push(Pos(nextY, nextX));
            checked[nextY][nextX] = true;
            dist[nextY][nextX] = dist[nowY][nowX] + 1; // 최단 거리 업데이트 (방문 노드에서 +1 하면 최단거리!)
        }
    }
        
    if (!checked[n - 1][m - 1]) // 도착지가 한번도 큐에 들어갔던적이 없다면 애초에 갈 수 없었던 곳이니 -1 리턴
        return -1;
    else
        return dist[n - 1][m - 1]; // 도착지의 최단경로 리턴
}

BFS를 사용하면 출발지 노드로부터 각각의 모든 노드들까지의 최단 경로로서 이동하게 된다.
각 노드까지의 최단 경로는 각 노드마다 딱 한번만 업데이트 된다. dist[i][j] 는 딱 한번만 업데이트 된다.

            /* 다음에 방문할 수 있는 곳이니 큐에 넣어 예약하기! -> ⭐그와 동시에 최단거리 업데이트⭐ */
            q.push(Pos(nextY, nextX));
            checked[nextY][nextX] = true;
            dist[nextY][nextX] = dist[nowY][nowX] + 1;

각 노드까지의 최단경로 업데이트는 큐에 넣을 때(예약 시) 이루어져야 한다.
- 현재 방문 중인 노드까지의 최단 경로에서 1 만 더해주면 되기 때문에 예약 작업에서 큐에 들어가자마자 최단 경로를 미리 업데이트 해주는 것이다. (큐에서 빠져나와 방문되기 전)

✈ 방문 순서

각각 예제 2, 예제 1의 노드별 BFS 방식으로 방문한 순서는 위와 같다.

✈ 최단 거리

BFS 를 모두 끝내면 예제 1 의 모든 노드의 출발지로부터의 최단 거리는 위와 같다.

🔥 두 번째 풀이 ⭕

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

struct Pos {
    int y;
    int x;
    int dist; // 거리
};

int solution(vector<vector<int> > maps)
{
    int answer = -1;
    
    const int n = maps.size();
    const int m = maps[0].size();
    int deltaY[4] = { -1, 0, 1, 0 };
    int deltaX[4] = { 0, 1, 0, -1 };

    vector<vector<bool>> checked(n, vector<bool>(m));
    queue<Pos> q;

    q.push({0, 0, 1}); // 출발지의 거리는 1
    checked[0][0] = true;

    while (!q.empty()) {
        Pos pos = q.front();
        q.pop();
        
        int nowY = pos.y;
        int nowX = pos.x;
        int now_dist = pos.dist;
        
        if (nowY == n - 1 && nowX == m - 1) // 목적지 원소(Pos) Pop될시 거리를 answer 에 옮겨주기
            answer = now_dist;

        for (int i = 0; i < 4; ++i) {
            int nextY = nowY + deltaY[i];
            int nextX = nowX + deltaX[i];

            if (nextY < 0 || nextY >= n || nextX < 0 || nextX >= m)
                continue;
            if (maps[nextY][nextX] == 0)
                continue;
            if (checked[nextY][nextX])
                continue;

            q.push({nextY, nextX, now_dist + 1}); // 거리 저장
            checked[nextY][nextX] = true;
        }
    }
        
    return answer;
}

첫번째 풀이와 차이점이 있다면 이 풀이는 dist 배열을 사용하지 않고 거리를 Pos 구조체 안에 저장했다는 것이다. 대신, 이렇게 하려면 큐에 들어가는 원소(구조체) 내부에 거리가 저장되는 것이기 때문에

answer의 초기값은 -1
큐의 원소인 Pos 구조체 내부의 dist 멤버에 거리가 저장되기 떄문에 Pos 구조체가 목적지일 때를 캐치하여 그 거리를 answer에 옮겨주는 작업을 추가로 해주어야 한다.
- 배열 테이블에 모든 지점별 거리들이 저장되는게 아니기 떄문이다. 원소(Pos 구조체 인스턴스)에 거리가 저장되어 있기 때문에 다음 while 문에서 큐에서 다른 원소를 Pop 함에 따라 이전 원소(Pos)의 거리는 잊혀진다. 따라서 목적지 Pos 에 도달시 따로 거리를 다른 변수에 저장해두는 작업이 필요하다.
목적지에 도달하지 못했다면(즉, while문 안에서 if 에 걸리지 못했다면) answer는 그대로 -1 인 상태일 것이다.

(C++) BFS 와 다익스트라의 거리 저장 및 업뎃

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

공부하는 식빵맘 👱‍♀️