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

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

DFS 문제 풀이 시 Check Point

1. 2차원 배열에서 최단 거리를 구해야하므로 dist[][]배열을 선언한다.

2. vector<vector<int>> 형 배열은 vector.size()가 행, vector[0].size()가 열이다.

3. (1,1) 좌표에서 시작하지만 사실상 (0,0)에서부터 탐색을 시작하므로 dist[n-1][m-1] 을 확인해야한다. 

4. 따라서 nx와 ny도 N,M과 동일하면 탐색하지않고 continue 한다. 

5. dist[][]의 값은 0으로 초기화하여 사용하자(memset으로 괜히 초기화했다가 효율성에서 탈락함)

 

#include<vector>
#include <iostream>
#include <queue>
#include <string.h>
#include <algorithm>

using namespace std;

int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
const int MAX = 101;

queue<pair<int,int>> Q;
bool visited[MAX][MAX];
int dist[MAX][MAX]={0};

int solution(vector<vector<int> > maps)
{  
    
    const int n=maps.size();
    const int m=maps[0].size();
    
    Q.push({0,0});
    dist[0][0]=1;
    visited[0][0]=true;
    
    while(!Q.empty()){
        int xx = Q.front().first;
        int yy = Q.front().second;

        Q.pop();

        for(int i=0;i<4;i++){
            int nx = xx +dx[i];
            int ny = yy +dy[i];
            
            if(nx<0||ny<0||nx>=n||ny>=m) continue;
            if(maps[nx][ny]==0||visited[nx][ny]) continue;
            
            Q.push({nx,ny});
            dist[nx][ny]=dist[xx][yy]+1;
            visited[nx][ny]=true;
        }
    }
    
    if (!dist[n-1][m-1]) return -1;
    else return dist[n-1][m-1];
}