[프로그래머스 LV 2] 게임 맵 최단거리

전형적인 BFS문제

BFS 문제를 풀어보면서 이런 맵 탐색이나 미로 탐색에는 큐를 써서 많이 푸는 것 같다.

 

1. 처음으로 방문처리와 거리값을 체크할 배열을 0으로 초기화해준다. (n,m은 각각 1 이상 100이하의 자연수여서 최대101개가 들어갈 수 있게 해준다.)

2. 반시계방향, 시계방향으로 돌면서 맵을 탐색할 때 쓸 방향 배열(x,y)을 선언해준다. 

3. 초기값을 큐에 넣어주고 while문과  for문을 통해 맵을 탐색하고 위치에서 이상이 있을때(지도사이즈 이상의 위치, 방문한 곳, 벽인지 체크) continue 해주고 각 위치에 대한 값을 넣어준다.

#include<vector>
#include<queue>
using namespace std;
int dx[4]={1,0,-1,0};       //반시계방향 아래부터
int dy[4]={0,1,0,-1};
int width,height;
bool visited[101][101]={0};
int bfs[101][101]={0};

queue<pair<int,int>> q;
int solution(vector<vector<int> > maps)
{
    int answer = 0;
    
    width=maps[0].size();           //가로
    height=maps.size();              //세로
    
    q.push({0,0});              //시작
    visited[0][0]=1;
    bfs[0][0]=1;
    
    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>=height||nx<0||ny>=width||ny<0) continue;     //사이즈 이상
            
            if(visited[nx][ny]) continue;           //방문여부 체크
                
            if(maps[nx][ny]==0) continue;              //벽인지 체크
            
            visited[nx][ny]=1;
            q.push({nx,ny});
            bfs[nx][ny]=bfs[curX][curY]+1;
        }
    }
    
    if(!bfs[height-1][width-1]) answer=-1;
    else answer=bfs[height-1][width-1];
    
    return answer;
}