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

1.문제 링크

게임 맵 최단거리

2. 풀이 전 계획과 생각

• bfs 혹은 dfs 이용하기

3. 풀이

#include<vector>
#include<queue>
using namespace std;

vector<vector<int> > map;
int map_cnt[100][100];
bool check[100][100];
int n,m;

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

void bfs(){
    int cnt=1;
    queue<pair<int, pair<int,int>> > q;
    q.push({cnt,{0,0}});
    check[0][0]= true;
    map_cnt[0][0]=cnt;
    cnt++;

    while(!q.empty()){
        int x = q.front().second.first;
        int y = q.front().second.second;
        int ocnt = q.front().first;
        q.pop();


        for(int i=0;i<4;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            int ncnt = ocnt+1;

            if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
            if(map[nx][ny]==0) continue;
            if(check[nx][ny]) continue;

            map_cnt[nx][ny]=ncnt;
            check[nx][ny]= true;
            q.push({ncnt,{nx,ny}});
        }

    }
}

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

    bfs();

    int answer = 0;
    if(map_cnt[n-1][m-1]==0) answer=-1;
    else answer=map_cnt[n-1][m-1];
    return answer;
}

1. maps 전역변수 map에 저장. n*m 사이즈를 구해 전역변수에 저장.

2. bfs함수.

3. 도착지 cnt정보가 0이라면 갈수 없는 경우이므로 -1을 아니라면 저장된 cnt값을 반환.

4. 풀이하면서 고민했던 점

• bfs를 써야할지 dfs써야할지 고민함. dfs를 사용했을 때 시간초과 문제가 발생해 bfs 사용했더니 해결됨.

5. 문제를 풀고 알게된 개념 및 소감

• dfs보다 bfs가 시간적인 면에서 더 효율적이라는 것을 알게됨.

• 어떤 한 문제에 대해서 bfs, dfs 풀이법이 가능하다는 것을 알게됨.