프로그래머스 게임 맵 최단경로

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

프로그래머스

문제 설명

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.

아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

• 첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.

 

• 두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.

위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.

---

 

이 문제는 캐릭터가 게임 맵에서 상대 팀 진영으로 이동하는 가장 빠른 길을 찾는 것이다. 이 문제는 너비 우선 탐색(BFS)을 사용하여 해결하는 것이 적합하다. 그 이유는 다음과 같다:

BFS 사용 이유:

1. 최단 거리 탐색: BFS는 시작 지점에서 가장 가까운 노드부터 탐색하기 때문에 최단 거리를 보장한다. 이 문제에서는 캐릭터가 상대 팀 진영으로 가는 최단 경로를 찾아야 하므로 BFS가 적합하다.
2. 탐색 경로의 모든 가능성 고려: BFS는 너비 우선으로 모든 인접한 노드를 탐색하므로, 모든 가능한 경로를 고려할 수 있다.

따라서 이 문제는 BFS를 사용하여 해결하는 것이 적합하다. 이제 BFS를 사용한 구체적인 알고리즘과 그 이유를 설명하겠다.

BFS 구체적 알고리즘:

1. 시작 위치를 큐에 넣는다. 큐에는 시작 위치와 이동한 칸의 개수를 함께 저장한다.
2. 큐에서 위치를 하나씩 꺼내며 인접한 위치를 탐색한다.
3. 벽이 아니고 방문하지 않은 위치라면 큐에 추가하고, 해당 위치까지의 이동한 칸의 개수를 갱신한다.
4. 상대 팀 진영에 도착한 경우, 해당 위치까지의 이동한 칸의 개수를 반환한다.
5. 큐가 빌 때까지 위 과정을 반복하며 도착하지 못한 경우 -1을 반환한다.

 

코드1

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

using namespace std;

// 상, 하, 좌, 우 이동을 위한 배열
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int solution(vector<vector<int> > maps) {
    int n = maps.size(); // 행의 개수
    int m = maps[0].size(); // 열의 개수
    
    queue<pair<pair<int, int>, int>> q; // BFS를 위한 큐
    vector<vector<bool>> visited(n, vector<bool>(m, false)); // 방문 여부를 저장하는 배열
    
    q.push({{0, 0}, 1}); // 시작 지점을 큐에 삽입
    visited[0][0] = true; // 시작 지점 방문 처리
    
    while (!q.empty()) {
        int x = q.front().first.first; // 현재 위치 x 좌표
        int y = q.front().first.second; // 현재 위치 y 좌표
        int dist = q.front().second; // 현재까지의 이동 거리
        q.pop();
        
        // 상대 팀 진영에 도착한 경우
        if (x == n - 1 && y == m - 1) {
            return dist; // 현재까지의 이동 거리를 반환
        }
        
        // 상, 하, 좌, 우 이동
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            // 다음 위치가 맵 안에 있고, 벽이 아니며, 방문하지 않은 곳인 경우
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && maps[nx][ny] == 1 && !visited[nx][ny]) {
                q.push({{nx, ny}, dist + 1}); // 다음 위치와 이동 거리를 큐에 삽입
                visited[nx][ny] = true; // 다음 위치 방문 처리
            }
        }
    }
    
    return -1; // 상대 팀 진영에 도달하지 못한 경우
}

q.push({{0, 0}, 1});

여기서 1은 시작 지점까지의 이동 횟수를 나타낸다.

**q.pop()**은 큐에서 현재 처리한 노드를 제거하는 작업이다.

BFS 알고리즘에서는 현재 처리한 노드에 대해 인접한 노드들을 방문하기 위해 큐를 사용한다. 큐에서 노드를 꺼낸 후에는 해당 노드에 대한 처리가 끝났으므로 큐에서 제거해야 한다.

이렇게 큐에서 노드를 꺼내고(pop) 처리를 한 후에는 해당 노드에 대한 작업이 완료되었으므로 큐에서 제거한다. 그 후에는 큐에서 새로운 노드를 꺼내어 처리하는 작업을 반복한다.

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

**dx**와 dy 배열은 각각 상, 하, 좌, 우로의 이동을 나타내는 배열입니다. 코드에서 **-1**은 상단으로 이동을 나타내고, **1**은 하단으로 이동을 나타냅니다. **0**은 좌우로의 이동을 나타냅니다.

이러한 표기법은 일반적으로 사용되는 방법입니다. 위로 이동하면 행의 인덱스가 감소하고, 아래로 이동하면 행의 인덱스가 증가합니다. 좌측으로 이동하면 열의 인덱스가 감소하고, 우측으로 이동하면 열의 인덱스가 증가합니다.

// 상, 하, 좌, 우 이동
for (int i = 0; i < 4; i++) {
    int nx = x + dx[i]; // 다음 위치의 행 좌표
    int ny = y + dy[i]; // 다음 위치의 열 좌표

    // 다음 위치가 맵 안에 있고, 벽이 아니며, 방문하지 않은 곳인 경우
    if (nx >= 0 && nx < n && ny >= 0 && ny < m && maps[nx][ny] == 1 && !visited[nx][ny]) {
        q.push({{nx, ny}, dist + 1}); // 다음 위치와 이동 거리를 큐에 삽입
        visited[nx][ny] = true; // 다음 위치 방문 처리
    }
}

• **nx**와 **ny**는 각각 다음 위치의 행과 열을 나타냅니다.
• **nx**와 **ny**가 맵의 범위 내에 있고, 해당 위치가 벽이 아니며 방문하지 않은 곳인지를 검사합니다.
• 만약 이동이 가능한 경우에는 해당 위치를 큐에 삽입하고, 다음 위치를 방문했다고 표시합니다.

이 코드는 상하좌우로의 이동 가능 여부를 확인하여, 이동이 가능한 경우에는 해당 위치를 큐에 넣고 이동 거리를 1 증가시키는 것을 반복합니다.

 

코드2

#include<vector>
#include<queue>

using namespace std;
int check[101][101];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int solution(vector<vector<int> > maps)
{
    int answer=0;
    int n=maps.size();
    int m=maps[0].size();
    
    queue<pair<int,int>>q;
    q.push(make_pair(0,0));
    check[0][0]=true;
    
    while(!q.empty()){
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        
          for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0<=nx && nx<n && 0<=ny && ny<m){
                if(check[nx][ny] == false && maps[nx][ny] > 0){
                    check[nx][ny] = true;
                    maps[nx][ny] = maps[x][y] + 1;
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }

    if(maps[n-1][m-1]==1){
        return -1;
    }
    else{
        answer=maps[n-1][m-1];
    }
    return answer;
}

주어진 코드는 BFS 알고리즘을 사용하여 게임 맵에서 상대 팀 진영으로 가는 최단 경로의 길이를 구하는 함수입니다. 코드의 각 부분을 설명해보겠습니다.

1. 먼저, **dx**와 dy 배열은 각각 상, 하, 좌, 우로의 이동을 나타냅니다. 이동 방향은 각각 **dx[i]**와 **dy[i]**로 나타내어집니다.
2. solution 함수에서는 BFS 알고리즘을 사용하여 최단 경로의 길이를 구합니다.
3. **queue<pair<pair<int,int>,int>> q**는 BFS 알고리즘을 위한 큐입니다. 큐에는 현재 위치와 해당 위치까지의 이동 거리가 함께 저장됩니다.
4. **vector<vector<bool>> visited**는 각 위치를 방문했는지를 나타내는 배열입니다. 방문한 위치는 **true**로 표시됩니다.
5. 시작 위치인 (0, 0)을 큐에 넣고 방문했음을 표시합니다.
6. 큐가 빌 때까지 반복문을 실행합니다. 반복문 내에서는 큐에서 현재 위치와 해당 위치까지의 이동 거리를 가져옵니다.
7. 만약 현재 위치가 상대 팀 진영에 도달한 경우에는 해당 위치까지의 이동 거리를 반환합니다.
8. 현재 위치에서 상하좌우로의 이동 가능한 경우를 검사합니다. 다음 위치가 맵 안에 있고, 벽이 아니며, 방문하지 않은 곳인 경우에는 해당 위치를 큐에 넣고 방문했음을 표시합니다.
9. 만약 상대 팀 진영에 도달하지 못한 경우에는 **1**을 반환합니다.