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

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

프로그래머스

 

queue를 사용한 BFS로 해결할 수 있다

현재 위치에서 다음 칸이 이동 가능한지 확인한 뒤
이동 가능하다면 queue에 push하여 탐색 대기열에 추가한다
이후 queue에서 순서대로 pop하며 탐색하면
시작 지점으로부터 가까운 위치부터 차례대로 탐색할 수 있다

이 문제는 특정 지점까지의 최단 거리를 구하는 문제이므로
가장 가까운 경로부터 탐색하는 BFS가 적합하다고 판단했다
반면 DFS는 한 방향으로 끝까지 탐색한 뒤 되돌아오는 방식이기 때문에
최단 거리를 보장하지 않으며 불필요한 경로까지 탐색할 가능성이 있다

#include <vector>
#include <queue>

using namespace std;

// 방향 벡터
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,1,0,-1 };

int bfs(vector<vector<int>>& maps, vector<vector<int>> isVisited, int startX, int startY)
{
    // queue 선언
    queue<pair<int,int>> q;

    // queue에 시작 지점 추가
    q.push({ 0,0 });

    // 시작 지점 방문 처리 (거리가 1)
    isVisited[0][0] = 1;

    // queue 순회
    while (!q.empty())
    {
        int curX = q.front().first;
        int curY = q.front().second;
        q.pop();

        // 우측 하단을 탐색하면 반환하고 종료
        if (curX == maps.size() - 1 && curY == maps[0].size() - 1)
        {
            return isVisited[maps.size() - 1][maps[0].size() - 1];
        }

        // 4방향 검사
        for (int i = 0; i < 4; i++)
        {
            int nx = curX + dx[i];
            int ny = curY + dy[i];

            // 미로 범위 체크
            if (nx >= 0 && nx < maps.size() && ny >= 0 && ny < maps[0].size())
            {
                // 벽 체크
                if (maps[nx][ny] != 0)
                {
                    // 방문 했는지 체크
                    if (isVisited[nx][ny] == -1)
                    {
                        // 거리 갱신
                        isVisited[nx][ny] = isVisited[curX][curY] + 1;

                        // queue 추가
                        q.push({ nx, ny });
                    }
                }
            }
        }
    }

    // 출구를 못 찾은 경우
    return -1;
}

int solution(vector<vector<int>> maps)
{
    int answer = 0;

    vector<vector<int>> isVisited(maps.size(), vector<int>(maps[0].size(), -1));
    answer = bfs(maps,isVisited,0,0);

    return answer;
}