[Graphs-BFS][Medium] 1926. Nearest Exit from Entrance in Maze

https://leetcode.com/problems/nearest-exit-from-entrance-in-maze/description

LeetCode - The World's Leading Online Programming Learning Platform

 

Q. 주어진 maze에서 '.'은 빈칸을, '+'은 벽을 의미한다.

 entrance에 있다고 가정하면, 출구까지의 최소 이동수를 구하라. 

 이때 출구는 외부 경계에 위치한 빈칸인 셀이다. 

 벽으로는 이동 할 수 없다. 

 

 

 

Solution

 비로소 graph를 이용한 경로를 탐색하는 실생활에 나올법한 문제다. 

 약간의 꼬임이 있지만, 문제도 깔끔하다. 

 

 시작점을 기준으로 갈 수 있는 영역으로 탐색을 전개 한다.

 exit에 도달하면 경로수를 기록하고 최소 경로수를 업데이트 한다.

 

 로직을 코드로 옮겨 본다. 

 

int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) 
{
    int mazeWidth = maze[0].size();
    int mazeHeight = maze.size();
    vector<bool> vVisit;
    vVisit.resize(mazeHeight * mazeWidth, false);

    // pair of (index, move count)
    queue<pair<int, int>> qBuff;	
    // entrance에서 0이 y, 1이 x에 해당함에 유의.    
    int idx = entrance[0] * mazeWidth + entrance[1];
    qBuff.push(make_pair(idx, 0));

    int minCount = INT_MAX;
    while (!qBuff.empty())
    {
        idx = qBuff.front().first;
        int moveCnt = qBuff.front().second;
        qBuff.pop();

        if (vVisit[idx])  continue;
        vVisit[idx] = true;

        int ix = idx % mazeWidth;
        int iy = idx / mazeWidth;
        if (maze[iy][ix] == '+')	continue;

        if (ix == 0 || ix == mazeWidth - 1 || iy == 0 || iy == mazeHeight - 1)
        {
            if (ix != entrance[1] || iy != entrance[0])
            {
                minCount = min(minCount, moveCnt);
                continue;
            }
        }

        // left
        if (ix > 0)	
            qBuff.push(make_pair(idx - 1, moveCnt + 1));

        // right
        if (ix < mazeWidth - 1)
            qBuff.push(make_pair(idx + 1, moveCnt + 1));

        // up
        if (iy > 0)
            qBuff.push(make_pair(idx - mazeWidth, moveCnt + 1));

        // down
        if (iy < mazeHeight-1)
            qBuff.push(make_pair(idx + mazeWidth, moveCnt + 1));
    }
    return minCount==INT_MAX ? -1 : minCount;
}

 

 

다소 최적화의 여지는 더 있어보이지만, 이정도에서 정리.