코딩테스트 : 게임 맵 최단거리 문제

해당 문제는 로봇이 목적지까지 갈 수 있는 최단거리를 구하는 문제이다. 처음 생각엔 목적지까지 가는 모든 경우의 수를 구하고 그 중에서 가장 작은 값이 최단거리니 재귀함수를 이용해 DFS 방법으로 해결하려고 하였다. 하지만 DFS를 사용하니 모든 경우의 수를 확인해야해서 시간 복잡도가 높게 나왔고 시간초과 문제와 테스트 케이스 19/21 정답률이 나왔다.

 

DFS에 대한 자세한 설명은 아래 링크에 정리해두었다.

DFS( Depth-First Search) 깊이 우선 탐색

첫 해결 방안(DFS)

#include <vector>
#include <set>

using namespace std;

//map은 변하지 않고 재귀함수로 매번 넘겨주지 않기 위해 전역변수로 선언
vector<vector<int>> map;

//currentPos : 현재 좌표를 pair로 저장.(x,y)
int Directions(pair<int,int> currentPos, set<int> s, int steps)
{
		//현재 위치가 맵 끝(목적지)에 도달 시 현재 걸음 수를 반환
    if(currentPos.first == map[0].size() - 1 && currentPos.second == map.size() - 1)
    {
        return steps;
    }
    
		//num은 Directions에서 목적지에 도달했을 때 최단거리를 비교하기 위해 나올 수 있는 가장 큰 수로 초기화
    int num = map[0].size() * map.size();
    
    //좌,우,상,하 로 이동 시 변화하는 좌표 저장
    vector<pair<int, int>> direction = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    
    //현재 위치에서 상하좌우 모두 반복
    for(pair<int, int> p : direction)
    {
        int nextX = currentPos.first + p.first;
        int nextY = currentPos.second + p.second;
        
        //다음 움직일 좌표가 맵을 벗어나지 않는지, 움직일 위치가 벽이 아닌지 판별
        if(nextX >= 0 && nextX < map[0].size() && nextY >= 0 && nextY < map.size() && map[nextY][nextX] != 0)
        {
		        //temp.size()와 s.size()를 비교해 왔던 위치인지 확인
		        //s는 거쳤던 경로를 저장하는데 set 특성상 같은 경로가 들어오면 size가 변하지 않음
            set<int> temp;
            temp = s;
            temp.insert(nextY * map[0].size() + nextX);
            
            //크기가 같다면 set에 같은 원소가 들어왔다는 뜻이므로 지나온 경로 방문으로 판단
            if(temp.size() != s.size())
            {
		            //Directions에 다음 위치와 경로를 담은 set, 현재 걸음 수를 넘겨준다.
		            //만약 목적지에 도달 시 소요한 걸음 수를 반환
                int n = Directions(make_pair(nextX, nextY), temp, steps + 1);
                //모든 경우를 돌아보며 가장 작은 steps 수 num에 저장
                num = num > n ? n : num;
            }
            
        }
    }
    
    return num;
}

int solution(vector<vector<int> > maps)
{
    map = maps;
    set<int> s = {0};
    
    int n = Directions(make_pair(0,0), s, 1);
    return n == map[0].size() * map.size() ? -1 : n;
}

하지만 해당 문제는 최단거리를 구하면 되는 문제로 가장 짧은 것을 구했을 때 종료하는 것이 가장 효율적인 방법이다. DFS는 모든 경우의 수를 확인하기 때문에 map이 클 경우 시간복잡도가 기하급수적으로 커진다.

 

때문에 한 단계씩 진행하다 가장 먼저 완료되면 해당 값을 구하는 BFS 그래프 탐색 알고리즘을 사용해야한다.

 

BFS에 대한 자세한 설명은 아래 링크에 정리해두었다.

BFS(Breadth-First-Search) 넓이 우선 탐색

두번째 해결 방안(BFS)

#include <vector>
#include <queue>

using namespace std;

int solution(vector<vector<int> > maps)
{
		//현재 위치와 현재 걸음 수 기록을 담는 queue
    queue<pair<pair<int, int>, int>> q;
    
    //현재 타일에 방문한 적이 있는지 확인하는 vector
    //만약 두번째로 방문하는 경우의 수가 있다면 해당 경우의 수는 전에 방문한 경우의 수보다
    //스텝이 많고 앞으로 갈 방향 같기 때문에 더이상 확인하지 않는다.
    vector<vector<bool>> visited(maps.size(), vector<bool>(maps[0].size(), false));
    //첫 플레이어 위치인 0,0은 방문
    visited[0][0] = true;
    
    //좌,우,상,하 로 이동 시 변화하는 좌표 저장
    vector<pair<int, int>> direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

		//첫 경우 q에 삽입
    q.push(make_pair(make_pair(0,0), 1));
    
    while(!q.empty())
    {
		    //현재 확인할 경우 꺼내고 삭제하기
        pair<pair<int, int>, int> currentPos = q.front();
        q.pop();
        
        //현재 좌표 보기 쉽게 할당
        int x = currentPos.first.first;
        int y = currentPos.first.second;
        
        //현재 걸음 수 보기 쉽게 할당
        int steps = currentPos.second;
        
        //현재 위치가 목적지 일때 현재 걸음 수 반환
        if(x == maps[0].size() - 1 && y == maps.size() - 1)
            return steps;
        
        //상하좌우로 움직인다.
        for(pair<int, int> p : direction)
        {
            int nextX = x + p.first;
            int nextY = y + p.second;
            
            //움직였는데 범위를 벗어나지 않고 방문하지 않은 타일이며 벽이 아닐 시
            if(nextX >= 0 && nextX < maps[0].size() && nextY >= 0 && nextY < maps.size() && visited[nextY][nextX] != true && maps[nextY][nextX] != 0)
            {
		            //현재 타일에 방문했다고 남기고
                visited[nextY][nextX] = true;
                //현재 위치로 이동한 후 q에 삽입
                q.push(make_pair(make_pair(nextX, nextY), steps + 1));
            }
        }
    }
    
    return -1;
}

BFS 알고리즘을 사용하면 모든 경우를 확인할 필요가 없기에 시간복잡도가 빨라진다.

 

★BFS 알고리즘은 최단 거리를 구하기에 유용하며 DFS는 모든 경우의 수를 확인한 후 작업할 때 유용하다.