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

 

캐릭터가 상대방 진영까지 가는데 걸리는 최단거리를 구하는 문제

제목 보고 그래프 문제인 줄 알고 시작했는데 알고보니 bfs 문제였다. 

하지만 아직 bfs도 숙련되지 못했기 때문에 푸는데 오래 걸렸다...

 

---

문제의 조건

 

1. 게임 맵에서 벽과 길을 표시한 2차원 배열 maps가 주어짐

 

2. maps에서 0은 벽이라서 지나갈 수 없고 1은 길이라서 지나갈 수 있다. 

 

3. 캐릭터의 초기 위치는 항상 [0,0] 이고 상대방 진영 위치는 항상 맵의 우측 하단이다. 

즉 상대방 진영 위치는 n x m 크기를 가진 maps 배열 상에서 [n-1, m-1] 이다. 

 

---

풀이 과정

 

1. bfs로 이동할 수 있는 다음 칸을 탐색하면서 다음 칸까지의 최단 거리를 계산한다. 

=> bfs로 이동할 다음 칸을 저장할 queue 필요

queue<pair<int, int>> queue;

 

=> 맵에서 각 칸 까지의 이동거리를 저장할 새로운 2차원 배열이 필요 

 

 

시작점에서부터 각 칸까지의 이동거리를 위와 같이 계산할 수 있도록 코드를 짜야 함

 

dist라는 이름을 가진 거리를 계산할 2차원 배열을 게임 맵과 같은 크기로 하나 만든다. 

int n = maps.size(); //맵의 세로 길이

int m = maps[0].size(); //맵의 가로 길이

vector<vector<int>> dist(n, vector<int>(m, 0)); 

dist 배열의 모든 원소는 0으로 초기화 함

 

bfs로 다음에 이동할 수 있는 칸을 탐색하면서 해당 칸에 이동거리를 저장하면 된다. 

 

 

2. 캐릭터가 다음으로 이동할 위치를 탐색할 때 현재위치를 기준으로 상하좌우 방향을 검사하기 때문에

이전에 방문했던 위치에 다시 방문할 수 있다. 

이전에 방문했던 위치에는 다시 방문하지 않도록 방문한 위치를 저장할 배열이 필요하다. 

 

처음에는 set<pair<int, int>>으로 방문 좌표를 저장하는 방식으로 했는데 

set에서 방문 좌표를 확인하는 과정에서 시간이 오래 걸린건지 시간초과 나고 몇몇 테스트 케이스는 통과하지 못해서 

dist 배열처럼 게임 맵과 같은 크기의 bool 배열을 만들어서 체크했다. 

 

vector<vector<bool>> visited(n, vector<bool>(m, false)); 

이렇게 만들어서 사용

 

캐릭터가 visited[n-1][m-1] 위치에 방문했다면 해당 인덱스 값을 true일 테니 최단 거리를 리턴하고

visited[n-1][m-1] = false면 방문하지 못한 것이니 -1을 리턴하면 된다. 

 

---

 

 

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

int solution(vector<vector<int>> maps)
{
    int n = maps.size();
    int m = maps[0].size(); //맵의 가로, 세로 길이

    vector<vector<int>> dir;
    dir.emplace_back(vector<int>{0,1});
    dir.emplace_back(vector<int>{0,-1});
    dir.emplace_back(vector<int>{1,0});
    dir.emplace_back(vector<int>{-1,0}); //기준 위치 상하좌우 탐색방향

    int answer = 0;

    queue<pair<int, int>> queue; //pair.first = x 좌표, pair.second = y 좌표
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    vector<vector<int>> dist(n, vector<int>(m, 0));

    visited[0][0] = true; //초기 위치는 방문했으니까 true로 시작
    dist[0][0] = 1; //초기 위치까지의 이동거리는 1부터 시작함 
    queue.emplace(make_pair(0, 0)); //캐릭터 초기 위치 0,0부터 시작

    while (!queue.empty())
    {
        int x = queue.front().first;
        int y = queue.front().second;
        queue.pop();

        //현위치 기준으로 상하좌우 방향으로 이동할 수 있는 칸을 탐색하는데 
        for (int i = 0; 4 > i; i++)
        {
            pair<int, int> nextPos = make_pair(x + dir[i][1], y + dir[i][0]);

            if (0 <= nextPos.first && m > nextPos.first //맵을 벗어나지 않으면서 
            	&& 0 <= nextPos.second && n > nextPos.second 
                && 1 == maps[nextPos.second][nextPos.first] //해당 위치가 길(1)이고
                && !visited[nextPos.second][nextPos.first]) //방문한 적 없으면 
            {
                //방문했다는 표시를 하고
                visited[nextPos.second][nextPos.first] = true;
                //다음 탐색의 기준위치로 설정해야 하니까 방문 예정 큐에 저장 
                queue.emplace(nextPos);
                //해당 위치까지의 누적 거리를 저장한다. 
                //1칸씩 이동하니까 현재 dist 배열에 저장된 값에 +1 해주면 됨 
                dist[nextPos.second][nextPos.first] = dist[y][x] + 1;
            }
        }
    }

    if (!visited[n-1][m-1]) //상대방 진영에 벽에 막혀서 못 갔으면 해당 위치는 false일 것임 
        answer = -1;
    else //true라면 상대방 진영에 갔다는 뜻이니까 위에서 저장해 온 최단거리 리턴 
        answer = dist[n-1][m-1];

    return answer;
}