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

문제

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

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

문제풀이

DFS, BFS에서 기본적인 문제이다.

queue<vector<int>>q를 이용하여 q[0]에는 y좌표, q[1]에는 x좌표, q[2]에는 이동한 칸수의 정보를 입력한다.

q가 빌 때까지 반복하여 while문을 탈출하면 목표지점에는 닿을 수 없으므로 -1을 return 하면 된다.

현재 y, x좌표에서 상, 하, 좌, 우로 이동할 때 벽이거나, 범위를 벗어나면 갈 수 없으므로 push를 하지 않는다.

방문한 적이 없고 벽이 아닌 갈 수 있는 곳일 때 q에 y, x, 이동 칸 수를 push 한다.

다음 칸이 입력받은 map의 맨 오른쪽 아래라면 도착한 것이므로 cnt+1을 return 하면 된다.

 

코드

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

vector<vector<bool>>visit;
vector<vector<int>>map;
int dy[] = { 0,0,1,-1 };
int dx[] = { -1,1,0,0 };

int BFS() {
    queue<vector<int>>q;
    visit[0][0] = true;
    q.push({ 0,0,1 });
    int y(0), x(0), cnt(0);
    int idx(0);
    while (!q.empty()) {
        y = q.front()[0];
        x = q.front()[1];
        cnt = q.front()[2];
        q.pop();

        for (idx = 0; idx < 4; ++idx) {
            int n_y(y + dy[idx]);
            int n_x(x + dx[idx]);
            if (n_y >= 0 && n_y < map.size() && n_x >= 0 && n_x < map[0].size()) {
                if (n_y == map.size() - 1 && n_x == map[0].size() - 1) {
                    return (cnt + 1);
                }
                if (!visit[n_y][n_x] && map[n_y][n_x]) {
                    q.push({ n_y,n_x,cnt + 1 });
                    visit[n_y][n_x] = true;
                }
            }
        }
    }
    return -1;
}

int solution(vector<vector<int> > maps)
{
    map = maps;
    visit = vector<vector<bool>>(maps.size(), vector<bool>(maps[0].size(), false));

    return BFS();
}