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

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "게임 맵 최단거리" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제는 ROR 게임에서 상대 팀 진영에 도달하기 위한 최단 경로를 찾는 문제입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크 : 

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

프로그래머스

문제 개요

"게임 맵 최단거리" 문제는 ROR 게임에서 상대 팀 진영에 도달하기 위한 최단 경로를 찾는 문제입니다. 게임 맵은 2차원 배열로 표현되며, 각 칸은 벽(0) 또는 이동 가능한 경로(1)입니다. 목표는 시작 지점(1,1)에서 종료 지점(n,m)까지 가장 빠른 경로를 찾는 것입니다.

해결 방법

이 문제는 너비 우선 탐색(BFS) 알고리즘을 사용하여 해결할 수 있습니다. BFS는 각 단계에서 모든 이웃을 탐색하며, 가장 짧은 경로를 찾는 데 효과적인 방법입니다.

코드 구현

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

int dy[] = {-1,0,1,0}; // 상, 우, 하, 좌 이동을 위한 y 좌표 변화량
int dx[] = {0,1,0,-1}; // 상, 우, 하, 좌 이동을 위한 x 좌표 변화량

// BFS 함수는 주어진 맵에서 최단 경로를 찾습니다.
int BFS(vector<vector<int>> &maps){
    queue<pair<int,int>> q; // 탐색을 위한 큐
    int n = maps.size(); // 맵의 행 크기
    int m = maps[0].size(); // 맵의 열 크기
    vector<vector<int>> table(n,vector<int>(m,0)); // 방문한 위치와 거리를 기록하는 테이블
    q.push({0,0}); // 시작 위치 큐에 삽입
    table[0][0] = 1; // 시작 위치 거리를 1로 초기화

    while(q.size()){
        pair<int,int> current = q.front();
        q.pop();
        for(int i = 0; i < 4; i++){ // 상, 우, 하, 좌 방향으로 탐색
            int ny = current.first + dy[i];
            int nx = current.second + dx[i];
            // 맵 범위를 벗어나거나, 벽을 만나거나, 이미 방문한 위치는 무시
            if(ny < 0 || nx < 0 || ny >= n || nx >= m || maps[ny][nx] == 0 || table[ny][nx]) 
                continue;
            table[ny][nx] = table[current.first][current.second] + 1; // 거리 업데이트
            q.push({ny,nx}); // 새 위치를 큐에 삽입
        }            
    }
    // 목표 지점에 도달한 경우 거리 반환, 그렇지 않으면 -1 반환
    return table[n - 1][m - 1] > 0 ? table[n - 1][m - 1] : -1;
}

// solution 함수는 주어진 게임 맵에서 BFS 함수를 호출하여 결과를 반환합니다.
int solution(vector<vector<int> > maps)
{
    int answer = BFS(maps);
    return answer;
}

코드 설명

이 코드는 주어진 게임 맵에서 BFS 알고리즘을 사용하여 시작 지점부터 종료 지점까지의 최단 경로를 찾습니다. 각 칸에 도달할 때마다 거리를 기록하고, 이를 통해 최단 경로를 찾습니다. 맵의 경계를 넘어가거나, 벽이 있는 칸은 탐색에서 제외됩니다. 최종적으로 목표 지점에 도달할 수 없는 경우 -1을 반환합니다.

결론

"게임 맵 최단거리" 문제는 BFS 알고리즘을 통해 효과적으로 해결할 수 있습니다. 이 알고리즘은 각 단계에서 모든 가능한 이동 경로를 고려하며, 가장 빠른 경로를 찾는 데 중요합니다. 이러한 접근 방식은 다양한 최단 경로 문제에 적용될 수 있습니다.