[Algorithm] Programmers :: 게임 맵 최단거리

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

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

struct Node
{
    Node(int _y, int _x) : y(_y), x(_x) {}
 
    int y;
    int x;
};
 
int solution(vector<vector<int> > maps)
{
    // 동서남북 방향이동
    int answer = 0;
 
    vector<vector<bool>> checkMap(maps.size() + 2, vector<bool>(maps[0].size() + 2)); // false
    vector<vector<int>> gameMap(maps.size() + 2, vector<int>(maps[0].size() + 2)); // 0
    vector<vector<int>> dir = { {0,1},{-1,0} ,{0,-1},{1,0} }; // 동서남북.
    
    // map 주위로 한겹 더 둘러싸기.
    for (int i = 0; i < maps.size(); i++)
    {
        for (int j = 0; j < maps[i].size(); j++)
        {
            gameMap[i + 1][j + 1] = maps[i][j];
        }
    }
 
    queue<Node> nodeQueue;
    Node startNode(1, 1);
    nodeQueue.push(startNode);
    int weight = 1;
    
    while (!nodeQueue.empty())
    {
        // 꺼내기
        Node popedNode = nodeQueue.front();
        nodeQueue.pop();
        checkMap[popedNode.y][popedNode.x] = true;
        
        // 꺼냈으니까 각 방향(동서남북) 자식노드들 큐에넣기
        for (int i = 0; i < dir.size(); i++)
        {
            int nextY = popedNode.y + dir[i][0];
            int nextX = popedNode.x + dir[i][1];
 
            // 해당지점이 벽이면(0이면) 노드 안만듬.
            if (gameMap[nextY][nextX] && !checkMap[nextY][nextX]) // 이동가능하면
            {
                checkMap[nextY][nextX] = true;
                gameMap[nextY][nextX] = gameMap[popedNode.y][popedNode.x] + 1;
 
                Node childNode(nextY, nextX);
                nodeQueue.push(childNode);
            }
        }
    }
 
    if (gameMap[maps.size()][maps[0].size()] == 1) return -1;
    else return gameMap[maps.size()][maps[0].size()];
}

기본적으로 탐색문제이긴 한데, 최소값을 구하는 문제라 BFS로 구현했다.

큐에서 노드를 꺼낼때마다 동,서,남,북에 이동할 수 있는지 체크한다. 체크할 때 해당 지점이 0(벽)이거나 맵을 벗어나는 위치면 이동하지 않는다. 즉, 큐에 해당 노드(자식노드)를 넣지 않는다.

위 코드같은 경우, 맵에 벽을 한겹 더 둘러서 실제 체크하는 코드를 0(벽)인지 아닌지만 체크하게 해놨다. 

if문부분에 코드를 길게 쓰고싶지 않기도 하고, 좀 더 직관적이라서 저렇게 짰다.

탐색하면서 maps에 해당 위치까지의 최단거리를 기록한다. 즉 해당 노드가 위치한 트리의 깊이값을 기록한다.

탐색이 끝난 후 NxM 지점값을 그대로 리턴하면된다. 값이 1 그대로면 탐색을 못했단거니까 -1을 리턴.

 

저렇게해도 잘 통과되긴하는데, 사실 탐색을 끝까지 마칠필욘없고, 목표지점을 탐색하는순간 무조건 최소값이기 때문에, 아래 코드처럼 바로 리턴하면 더 빨리 찾을 수 있다.

 

struct Node
{
    Node(int _y, int _x) : y(_y), x(_x) {}
 
    int y;
    int x;
};
 
int solution(vector<vector<int> > maps)
{
    // 동서남북 방향이동
    int answer = 0;
    int row = maps.size();
    int column = maps[0].size();
 
    vector<vector<bool>> checkMap(maps.size() + 2, vector<bool>(maps[0].size() + 2)); // false
    vector<vector<int>> gameMap(maps.size() + 2, vector<int>(maps[0].size() + 2)); // 0
    vector<vector<int>> dir = { {0,1},{-1,0} ,{0,-1},{1,0} }; // 동서남북.
    
    // map 주위로 한겹 더 둘러싸기.
    for (int i = 0; i < maps.size(); i++)
    {
        for (int j = 0; j < maps[i].size(); j++)
        {
            gameMap[i + 1][j + 1] = maps[i][j];
        }
    }
    queue<Node> nodeQueue;
    Node startNode(1, 1);
    nodeQueue.push(startNode);
    int weight = 1;
    
    while (!nodeQueue.empty())
    {
        // 꺼내기
        Node popedNode = nodeQueue.front();
        nodeQueue.pop();
        checkMap[popedNode.y][popedNode.x] = true;
        
        // 꺼냈으니까 각 방향(동서남북) 자식노드들 큐에넣기
        for (int i = 0; i < dir.size(); i++)
        {
            int nextY = popedNode.y + dir[i][0];
            int nextX = popedNode.x + dir[i][1];
 
            // 해당지점이 벽이면(0이면) 노드 안만듬.
            if (gameMap[nextY][nextX] && !checkMap[nextY][nextX]) // 이동가능하면
            {
                checkMap[nextY][nextX] = true;
                gameMap[nextY][nextX] = gameMap[popedNode.y][popedNode.x] + 1;
 
                if (checkMap[row][column]) return gameMap[row][column]; // 목표지점이면 바로 리턴
 
                Node childNode(nextY, nextX);
                nodeQueue.push(childNode);
            }
        }
    }
 
    return -1;
}