프로그래머스 게임 맵 최단거리 C++

문제 설명

 

 

제한사항

• maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
  • n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
• maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
• 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

---

입출력 예

mapsanswer

[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]	11
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]	-1

입출력 예 설명

입출력 예 #1
주어진 데이터는 다음과 같습니다.

캐릭터가 적 팀의 진영까지 이동하는 가장 빠른 길은 다음 그림과 같습니다.

따라서 총 11칸을 캐릭터가 지나갔으므로 11을 return 하면 됩니다.

입출력 예 #2
문제의 예시와 같으며, 상대 팀 진영에 도달할 방법이 없습니다. 따라서 -1을 return 합니다.

 

 

=> 최단거리를 구하는 문제이기에 BFS를 활용하면 쉽게 풀 수 있습니다. 

=> 해당문제를 풀며 주의할 점은 두 가지입니다. 

저에게만 해당되는 점일수도 있습니다.

 

• 배열을 탐색할때 탐색할 수 없는 부분을 탐색하지 않는지 확인하기 (  ex) map [-2][0] ) 
• 위와 같은 오류를 범했을 때 segmentation fault ERROR가 발생합니다. 
• 탐색할 수 있는 구역을 정할때 행과 열을 헷갈리지 않기 
• 위와 같은 오류를 범하지 않기 위해 저는 그림을 그리고 그대로 풀이에 옮기는 방식을 취하고 있습니다. 

 

탐색할 부위를 미리 그림으로 그려보는 예시

 

해당 문제는 BFS코드 예제를 보며 대입하며 풀 수 있습니다. 

또한 백준알고리즘의 비슷한 다른 문제풀이를 올려두겠습니다. 

 

https://codingham.tistory.com/168

DFS, BFS code

https://codingham.tistory.com/319

백준 나이트의 이동 C++

 

 

 

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

using namespace std;

int M,N; // 행, 열
bool check[101][101]={0}; // 갔다왔는지 check하는 배열 
int bfsMap[101][101] = {0}; //BFS진행하며 진행거리를 체크함

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1}; //아래, 오른, 위, 왼

queue<pair<int, int>> q;
int solution(vector<vector<int> > maps)
{
    int answer = 0;
    
    N = maps[0].size();
    M = maps.size();
    
    //시작점 시작점 대입
    q.push(make_pair(0,0));
    check[0][0] = true;
    bfsMap[0][0]=1;
   
    //bfs시작
    while(!q.empty())
    {
        int curX = q.front().first;
        int curY = q.front().second;
        
        q.pop();
       
        for(int i=0; i<4; i++)
        {
            int nx = curX + dx[i];
            int ny = curY + dy[i];
           
            if(nx<0 || nx >= M || ny <0 || ny >= N) continue; // 움직일 수 있는 범위를 벗어난 경우
            
            if(check[nx][ny])continue; //갔다온 곳인 경우
            
            if( (maps[nx][ny] == 0))continue; //갈 수 있는 구역이 아닌 경우
               
            check[nx][ny] = true;
            q.push(make_pair(nx,ny));
            bfsMap[nx][ny] = bfsMap[curX][curY]+1;
            
        }
    }
    
    if(!bfsMap[M-1][N-1]) answer = -1;
    else  answer = bfsMap[M-1][N-1];
    
    return answer;
}