[프로그래머스 게임 맵 최단거리] c++ (코드,풀이, bfs)

문제 링크

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

프로그래머스

 

문제

 

코드 및 풀이

 

이 문제는 최단거리를 구하는 문제이므로 bfs를 채택하였습니다.

 

보통 최단,최소 라는 키워드를 그림판과 같은 형태 혹은 간선과 노드 같은 문제에서 BFS를 대표적으로 사용하는 것 같습니다.

 

게임 맵 안에 있는 유효한 새로운 y,x좌표라면

visited[새로운 y좌표][새로운 x좌표]  = visited[원래 y좌표][원래 x좌표] + 1 을 진행한 후

 

가장 먼저 ny == n - 1 && nx == m - 1이 되는 경우에 visited[ny][nx]를 return 해주었습니다.

 

이 bfs가 만약 다 비워지게 되면서 반복문이 끝나게 된다면 그것은 결국 좌표에 도달할 수 없다는 판단하에 -1을 리턴하였습니다.

 

/*

게임 맵 최단거리

누가 봐도 bfs로 풀어라! 하고 주는 문제 같은데

0,0에서 시작하고 n-1,m-1일때 도착

*/

#include<vector>

#include<queue>

using namespace std;

int solution(vector<vector<int>> maps)

{

    int answer = 0;

   

    //동서남북

    int dy[4] = {0,0,1,-1};

    int dx[4] = {1,-1,0,0};

    queue<pair<int,int>> q;

    int n = maps.size(); //행

    int m = maps[0].size(); //열

    int visited[100][100] ={0,};

   

    q.push(make_pair(0,0));

    visited[0][0] = 1;

   

    while(!q.empty()){

       

        //흔한 bfs방법으로 y,x를 뽑아내고 pop

        int y = q.front().first;

        int x = q.front().second;

        q.pop();

       

        //동서남북에 대해서 갈 수 있는지에 대한 체킹

        for(int i = 0; i < 4; i ++){

            int ny = y + dy[i];

            int nx = x + dx[i];

            if(0 <= ny && ny < n && 0 <= nx && nx < m){

                if(maps[ny][nx] == 1&& visited[ny][nx] == 0){

                    q.push(make_pair(ny,nx));

                    visited[ny][nx]= visited[y][x] + 1;

                    if(ny == n - 1 && nx == m - 1)

                        return visited[ny][nx];

                }

            }

        }

    }

    return -1;

}