프로그래머스[Level2] 게임 맵 최단거리 (BFS 알고리즘)

문제 설명

입출력 예시

 

 

------------------------------------------------------------------------------------------------------------------------------------------------

 

문제 접근 방법

 

1. 최단 경로를 찾으면서 모든 경로를 탐색해야 하므로  BFS 알고리즘을 사용하였습니다.

 

2. 문제 풀이 중 각 인덱스 초과의 경우 및 갔던 곳은 재방문 하지 않도록 해야 최단경로 이므로 길을 지나갈 때 마다 

    이전 "경로 비용 + 1"   을 하여 경로 비용을 계산하였습니다.

 

------------------------------------------------------------------------------------------------------------------------------------------------

 

코드 

 

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

int solution(vector<vector<int> > maps)
{
    int answer = 0;
    
    
    int iTargetRow = maps.size()-1;
    int iTargetCol = maps[0].size()-1;
    
    deque<pair<int,int>> m_deque; 
    m_deque.push_back({0,0});
    
    
    int dx[4] = {-1,1,0,0};
    int dy[4] = {0,0,-1,1};
    
    while(!m_deque.empty())
    {
        int row = m_deque.front().first;
        int col = m_deque.front().second; 
        
        m_deque.pop_front(); 
        
        // 동서남북 체크하고 -1 넣기
        
        // 이미 지나온 경로이거나 벽인경우 스킵
        for(int i=0; i<4; i++)
        {
            int Number_Row =  row+dx[i];
            int Number_Col =  col+dy[i];
                
            if( Number_Row < 0 || Number_Row >= maps.size()
                 || Number_Col < 0 || Number_Col >= maps[0].size()
                 || maps[Number_Row][Number_Col] == 0 
                 || maps[Number_Row][Number_Col] > 1)
            {
                continue; 
            }
            
            m_deque.push_back({Number_Row,Number_Col});
            maps[Number_Row][Number_Col] = maps[row][col] +1; 
            
            if( Number_Row == iTargetRow
               && Number_Col == iTargetCol)
            {
                return maps[Number_Row][Number_Col]; 
            }
            
        }
       
    }
    
    answer = -1; 
    
    return answer;
}