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

문제

 

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

프로그래머스

 

문제풀이

 

(1, 1) 위치에서 부터 시작하여 (N, M) 위치에 도달하는 모든 경우의 수 중 가장 짧은 길이를 찾는 문제이다.

최단거리를 구하는 문제이므로 BFS를 이용했다.

 

구조체를 선언하여 y, x의 좌표와, 거리를 나타내는 dist 변수를 둔다.

방문 벡터를 선언하여 이전에 방문한 적이 있는지 확인을 한다.

 

큐에 시작 지점을 집어넣고 큐가 빌 때까지 반복을 한다.

상, 하, 좌, 우 한 칸씩 이동한다.

만약 범위를 벗어나거나 이미 방문을 했다면 큐에 push를 하지 않고 넘어간다.

만약 다음칸이 도착지점이라면 거리를 return 한다.

 

큐가 빌 때까지 return을 한 적이 없으면 벽이 있어 도착지점에 갈 수 없는 경우이므로 -1을 return 한다.

코드

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

struct Coord {
    int y;
    int x;
    int dist;
};

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

int solution(vector<vector<int> > maps)
{
    int N = maps.size(), M = maps[0].size();
    vector<vector<bool>>visited(N, vector<bool>(M, false));
    queue<Coord>q;
    Coord start;
    start.y = 0, start.x = 0, start.dist = 1;
    q.push(start);
    visited[0][0] = true;

    while (!q.empty()) {
        int y = q.front().y;
        int x = q.front().x;
        int dist = q.front().dist;
        q.pop();

        for (int idx = 0; idx < 4; ++idx) {
            int ny = y + dy[idx];
            int nx = x + dx[idx];
            if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
            if (visited[ny][nx] == true) continue;
            if (ny == N - 1 && nx == M - 1) return dist + 1;
            if (maps[ny][nx] == 0) continue;
            visited[ny][nx] = true;
            Coord coord;
            coord.y = ny, coord.x = nx, coord.dist = dist + 1;
            q.push(coord);
        }
    }

    return -1;
}