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

풀이과정

BFS를 이용해서 최단경로 구할 수 있음

처음 (0,0)을 시작하므로 (0,0)에 대한 방문체크와 path를 1로 추가해준다.

이후 현재 좌표에서 상(-1,0), 하(1,0), 좌(0,-1), 우(0,1)가 유효한지 체크한 후, 방문하지 않았고 벽이 아니면 방문체크 후 인접노드에서 1 간 것과 같으므로 1을 더해서 path를 구한다.

탐색이 끝난 후 마지막 좌표(n,m)에 값이 들어있지 않으면 도달할 수 없는 것이므로 -1을 리턴하고, 값이 있으면 도달할 수 있으므로 값을 리턴한다.

 

제출코드

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

using namespace std;

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int path[101][101]={0,};
int visited[101][101]={0,};

int solution(vector<vector<int> > maps)
{
    int answer = 0;
    queue<pair<int, int>> q;
    
    int n = maps.size();
    int m = maps[0].size();  
    
    visited[0][0] = 1;
    path[0][0] = 1;
  
    q.push({0, 0});
    
    while(!q.empty()){
        int cx = q.front().first;
        int cy = q.front().second;
        
        q.pop();
        
        for(int i=0; i<4; i++){
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            
            if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if(maps[nx][ny] == 1 && visited[nx][ny] == 0){
                visited[nx][ny] = 1;
                q.push({nx,ny});
                path[nx][ny] = path[cx][cy] + 1;
            }
        }
    }
    
    if(path[n-1][m-1] == 0) answer = -1;
    else answer = path[n-1][m-1];
    
    return answer;
}

 

제출결과