프로그래머(깊이/너비 우선 탐색; 게임 맵 최단거리) c++

#include<vector>
#include<queue>
using namespace std;

int solution(vector<vector<int> > maps)
{
    int n = maps.size(), m = maps[0].size();
    vector<vector<bool>> bvisited(n, vector<bool>(m , false));
    queue<pair<int, int>> q;
    
    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};
    
    q.push({0, 0});
    bvisited[0][0] = true;
    
    while(!q.empty())
    {
        auto [r, c] = q.front();
        q.pop();
        
        for(int i = 0; i < 4; ++i)
        {
            int nr = r + dr[i];
            int nc = c + dc[i];
            
            if(nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
            if(bvisited[nr][nc] || maps[nr][nc] == 0) continue;
            
            bvisited[nr][nc] = true;
            maps[nr][nc] = maps[r][c] + 1;
            q.push({nr, nc});
        }
    }
    
    if(maps[n-1][m-1] == 1) return -1;
    return maps[n-1][m-1];
}

 

해설:

맵의 최단거리를 반환해야 한다. 그래서 지나간 위치에는 해당 이동거리만큼의 해당 위치에 값을 대입하여 반환시 해당 위치의 값이 1일 경우 -1을 반환하며 아닐경우 해당 이동거리 수만큼의 값을 반환한다.

 

첫번째: n(행 크기), m(열 크기), bvisited(방문), q(마지막 위치; LIFO인 queue를 사용하기 위해 #include <queue>를 선언해주고 pair를 통해 쌍배열로 선언)를 선언한다.

두번째: dr(direction row; 행 방향), dc(direction col; 열 방향)을 지정하여 나중에 나올 for문에서 각 위치에 맞게 이동할 수 있도록 해주며 현재 위치가 bvisited[0][0]에 있으므로 true로 변환.

세번째: q.empty() 될때까지 반복문을 돌려주며(마지막에 도착하면 조건문을 통해 continue로 넘어가기때문에 아무것도 실행되지 않는다.) 맨 처음 위치를 가져오기위해 q.front를 이용해 가져와주며 pop()을 통해 무한 루프를 방지한다.

네번쨰: 반복문을 통해 nr(next row), nc(next col)을 선언하여 다음 이동할 위치를 얻어낸다. 그 후 조건문들을 통해 다음 위치가 범위를 벗어나거나 다음 위치가 이미 방문했거나 0(이동할 수 없음)이면 continue로 다른 다음 이동 위치를 얻어낸다.

다섯번째: 위에 조건을 다 통과할 경우 bvisited[nr][nc]를 true로 변환 그리고 지금 해당 위치에는 +1로 이동할때마다 1을 누적하여 총 이동거리 수를 대입한다. 그런 다음 q.push({nr, nc})를 통하여 이동 위치들을 기록한다(그래야 for문이 끝난 후 다시 while문 상단으로 올라갔을때 현재 위치들을 대입할 수 있기 때문).

 

이제 마지막으로 위에서 설명한것과 같이 반환하면 끝이다.