(C++) - 프로그래머스(찾아라 프로그래밍 마에스터) : 게임 맵 최단거리

programmers.co.kr/learn/courses/30/lessons/1844

코딩테스트 연습 - 게임 맵 최단거리

bfs문제였습니다.

 

풀이방법

 1. bfs 수행 : d배열을 선언해서 0,0에서 출발하여 벽이 아닌 부분을 이동하며 거리를 저장합니다.

 2. 도착했을 때 해당 부분의 값이 0이라면 갈수 없으므로 -1을 반환합니다. 아니라면 d[n-1][m-2]를 반환합니다.

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;

int dr[] = {0, 0, 1, -1};
int dc[] = {1, -1, 0, 0};
int ck[101][101], n, m;

int bfs(vector<vector<int>> maps){
    queue <pii> q;
    q.push({0,0});
    ck[0][0] = 1;
    while(!q.empty()){
        int r = q.front().first;
        int c = q.front().second;
        q.pop();
        if(r == n - 1 && c == m - 1) return ck[r][c];
        for(int i = 0; i < 4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];
            if(0 > nr || nr >= n || 0 > nc || nc >= m) continue;
            if(ck[nr][nc] || !maps[nr][nc]) continue;
            ck[nr][nc] = ck[r][c] + 1;
            q.push({nr,nc});
        }
    }
    return -1;
}

int solution(vector<vector<int>> maps){
    n = maps.size();
    m = maps[0].size();
    memset(ck, 0, sizeof(ck));
    return bfs(maps);
}