찾아라 프로그래밍 마에스터: 게임 맵 최단거리(C++)

programmers.co.kr/learn/courses/30/lessons/1844

코딩테스트 연습 - 게임 맵 최단거리

해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다.

2차원 배열이 주어지고 최단거리를 묻는 문제이다.

 

풀이법

1) BFS에 count 변수를 넣어서 풀면 최단거리를 구할 수 있다.

2) 배열의 크기를 확인 한 후, 방문하지 않은 노드와 들어갈 수 없는 값들을 제외하고 BFS를 순회시킨다.

3) vx와 vy 배열을 사용하여 대각선이 아닌 상하좌우로 움직일 수 있도록 설정해준다.

4) 불가능한 값에 도달하는 경우, queue에 넣지 않으며, 도착지에 도달하는 경우 answer 값에 담아 return 한다.

#include<vector>
#include<queue>
using namespace std;
bool arr[101][101];
int vx[4]={-1,0,1,0};
int vy[4]={0,1,0,-1};

int solution(vector<vector<int>> maps)
{
    int answer = -1;
    int n=maps.size();
    int m=maps[0].size();
    queue<pair<int,pair<int,int>>> q;
    q.push({1,{1,1}});
    arr[1][1]=true;
    while(!q.empty())
    {
        int tx=q.front().first;
        int ty=q.front().second.first;
        int count=q.front().second.second;
        q.pop();
        if(tx==n && ty==m)
        {
            answer=count;
            break;
        }
        for(int i=0; i<4;i++)
        {
            int ux=tx+vx[i];
            int uy=ty+vy[i];
            if(arr[ux][uy]==1)
                continue;
            if(ux>=1 && ux<=n && uy>=1 && uy<=m)
            {
                if(arr[ux][uy]==0&& maps[ux-1][uy-1]==1)
                {
                    arr[ux][uy]=true;
                    q.push({ux,{uy,count+1}});
                }
            }
        }
    }
    
    
    return answer;
}

참고사항)

- 배열의 행을 수를 구할 때는, int n=maps.size()

- 배열의 열의 수를 구할 때는, int m=maps[0].size() 를 활용하면 된다.

- bool arr 배열을 만들어 방문한 곳을 다시 방문하는 것을 막는다.

- 넣을 수 있는 새로운 좌표를 각각 ux, uy라 할때, 1<=ux<=n && 1<=uy<=m 인 경우만 고려해야 한다.

- 방문하지 않았으며(arr[ux][uy]==0), 길이 있는 경우(maps[ux-1][uy-1]==1) queue에 값을 넣어준다.

   -- maps[ux-1][uy-1] : 문제에서 주어진 배열의 시작은 (0,0)이나 캐릭터의 시작 위치는 (1,1)이다 이를 고려해야 한다.