프로그래머스 [level 2] 게임 맵 최단거리 - 1844 (BFS)

문제

#include<vector>
#include <deque>
#include <iostream>
#include <algorithm>

using namespace std;

int solution(vector<vector<int> > maps)
{
    int n = maps.size(); 
    int m = maps[0].size(); 

    int i_Count = 0; 

    vector<vector<int>> m_vecVisit(n, vector<int>(m,-1));

    deque<pair<int,int>> m_dequeVisit; 
    m_dequeVisit.push_front({0,0});
    
    m_vecVisit[0][0] = 1; 

    while(!m_dequeVisit.empty())
    {
        int i_PosX = m_dequeVisit.front().first; 
        int i_PosY = m_dequeVisit.front().second; 

        m_dequeVisit.pop_front(); // 빼주기  


        if (i_PosX == n-1 && i_PosY == m-1)
        {
            return  m_vecVisit[i_PosX][i_PosY]; 
        }
        
        // 4 가지 경우 나누기 ( 동 서 남 북 ) 
        if(i_PosX - 1 >= 0)
        {
           if(maps[i_PosX-1][i_PosY] == 1 && m_vecVisit[i_PosX - 1][i_PosY] == -1)
           {
               m_dequeVisit.push_back({ i_PosX - 1 ,i_PosY });
               m_vecVisit[i_PosX - 1][i_PosY] = m_vecVisit[i_PosX][i_PosY] + 1; 
           }
        }

        if (i_PosX + 1 < n)
        {
            if (maps[i_PosX + 1][i_PosY] == 1 && m_vecVisit[i_PosX + 1][i_PosY] == -1)
            {
                m_dequeVisit.push_back({ i_PosX + 1 ,i_PosY });
                m_vecVisit[i_PosX + 1][i_PosY] = m_vecVisit[i_PosX][i_PosY] + 1; 
            }
        }
        

        if (i_PosY - 1 >= 0)
        {
            if (maps[i_PosX][i_PosY -1] == 1 && m_vecVisit[i_PosX][i_PosY - 1] == -1)
            {
                m_dequeVisit.push_back({ i_PosX ,i_PosY - 1 });
                m_vecVisit[i_PosX][i_PosY -1 ] = m_vecVisit[i_PosX][i_PosY] + 1; 
            }
        }


        if (i_PosY + 1 < m)
        {
            if (maps[i_PosX][i_PosY + 1] == 1 && m_vecVisit[i_PosX][i_PosY + 1] == -1)
            {
                m_dequeVisit.push_back({ i_PosX ,i_PosY + 1 });
                m_vecVisit[i_PosX][i_PosY + 1] = m_vecVisit[i_PosX][i_PosY] + 1; 
            }
        }

    }


    return -1; 
}

 

 

문제 접근 순서

 

1. 문제를 보니 동서남북으로 모든 곳을 탐색해야 하고 가장 빠른 길을 찾아야 하므로 BFS 알고리즘이 옳다고 생각함. 

 

2. 구현하기 위해서 모든 경우의 수를 deque 자료구조에 넣고 방문 기록을 vector 2차원 배열로 구현. 

 

3. 인덱스 요소가 혹시라도 범위를 벗어날 수 있으므로 먼저 if문으로 체크를 하기로 생각.