게임 맵 최단거리

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

프로그래머스

 

풀이 : 

#include<vector>
using namespace std;


void DFS(const vector<vector<int>>& _Maps, int _X, int _Y, int _TargetX, int _TargetY, unsigned int& _Answer, vector<vector<bool>>& _Visited, int _MoveCount = 1)
{
    if (_Maps.size() <= _Y || _Y < 0 || _Maps[0].size() <= _X || _X < 0)
    {
        return;
    }

    if (_Maps[_Y][_X] == 0 || _Visited[_Y][_X] == true)
    {
        return;
    }

    if (_X == _TargetX && _Y == _TargetY)
    {
        if (_Answer > _MoveCount)
        {
            _Answer = _MoveCount;
        }
        
        return;
    }

    _Visited[_Y][_X] = true;

    // 오른쪽, 아래, 왼쪽, 위
    DFS(_Maps, _X + 1, _Y, _TargetX, _TargetY, _Answer, _Visited, _MoveCount + 1);
    DFS(_Maps, _X, _Y + 1, _TargetX, _TargetY, _Answer, _Visited, _MoveCount + 1);
    DFS(_Maps, _X - 1, _Y, _TargetX, _TargetY, _Answer, _Visited, _MoveCount + 1);
    DFS(_Maps, _X, _Y - 1, _TargetX, _TargetY, _Answer, _Visited, _MoveCount + 1);

    _Visited[_Y][_X] = false;
}

int solution(vector<vector<int>> maps)
{
    unsigned int answer = -1;

    int Mapsize = maps.size() * maps[0].size();

    vector<vector<bool>> Visited(maps.size(), vector<bool>(maps[0].size(), false));

    DFS(maps, 0, 0, maps[0].size() - 1, maps.size() - 1, answer, Visited);

    return answer;
}

 

설명 : 

1.  visited배열 추가:
   1. visited배열을 사용하여 각 위치가 이미 방문되었는지 여부를 기록합니다.
2. 방문 표시 :
   1. 재귀 호출전에 visited[_Y][_X] = true로 방문했음을 표시합니다.
3. 방문 해제 :
   1. 재귀 호출이 끝난 후  visited[_Y][_X] = false로 다시 방문하지 않은 상태로 되돌려놓습니다. 이는 다른 경로 탐색 시 영향을 주지 않기 위함입니다.
4. 도달할 수 없는 경우 처리 :
   1. DFS가 종료된 후 answer가 여전히 -1 이면 목표 지점에 도달할 수 없음을 의미하므로, 이 경우 -1을 반환합니다.
5. 결론 : DFS로 문제를 풀었지만, 효율성 테스트에서 모두 부적격을 받아서 DFS가 아닌 BFS로 문제를 다시 풀어봐야한다.

 

BFS 풀이:

#include <vector>
#include <queue>
#include <utility> // for std::pair

using namespace std;

int solution(vector<vector<int>> maps) {
    int n = maps.size();
    int m = maps[0].size();
    
    // 방향 배열: 상, 하, 좌, 우
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    
    // 방문 체크 배열
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    
    // 시작점 방문 처리
    queue<pair<int, int>> q;
    q.push({0, 0});
    visited[0][0] = true;
    
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        // 4방향 탐색
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            // 지도 범위를 벗어나거나, 벽이거나, 이미 방문한 경우 무시
            if (nx < 0 || ny < 0 || nx >= n || ny >= m || maps[nx][ny] == 0 || visited[nx][ny])
                continue;
            
            // 방문하지 않은 경로면 이동 거리 갱신 및 큐에 추가
            maps[nx][ny] = maps[x][y] + 1;
            visited[nx][ny] = true;
            q.push({nx, ny});
        }
    }
    
    // 상대팀 진영에 도달했으면 최단 거리 반환, 그렇지 않으면 -1 반환
    if (maps[n-1][m-1] > 1)
        return maps[n-1][m-1];
    else
        return -1;
}

 

풀이 : 

1. 큐를 사용한 BFS 탐색:
   • queue<pair<int, int>> q를 사용하여 BFS를 구현합니다.
   • 초기 위치 (0, 0)을 큐에 넣고 시작합니다.
2. 4방향 탐색:
   • 각 위치에서 상하좌우 4방향으로 이동할 수 있는지 확인합니다.
   • 이동 가능하고 아직 방문하지 않은 경우, 그 위치의 값을 현재 위치 값에 1을 더한 값으로 업데이트합니다. 그리고 그 위치를 큐에 추가합니다.
3. 최단 경로 갱신:
   • BFS는 먼저 방문한 경로가 항상 최단 경로임을 보장합니다. 따라서 처음으로 목표 위치에 도달한 경우가 최단 거리입니다.
4. 결과 반환:
   • 목표 위치 (n-1, m-1)의 값이 변경되었다면 최단 거리를 반환하고, 그렇지 않다면 -1을 반환합니다.

시간 복잡도:

• BFS는 각 노드를 한 번씩만 방문하므로 시간 복잡도는 O(n * m)입니다. 이 방법은 큰 입력 크기에 대해서도 매우 효율적입니다.

결론:

이 BFS 코드는 효율성 테스트를 통과할 가능성이 높습니다. DFS와 달리 BFS는 모든 경로를 탐색하지 않고, 최단 경로만 탐색하므로 큰 입력에 대해서도 더 빠르게 결과를 도출할 수 있습니다.