[프로그래머스/c++] Lv2 게임 맵 최단거리

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

프로그래머스

bfs 문제이다. 

 

vector<vector<int>> graph(n, vector<int>(m,0));

--> 이 구문은 이미 왔던 길인지 확인하기 위해 2차원 벡터를 정의하고 모든 행열을 0으로 초기화한 것이다. 사실 bool isVisited로 구분할 수 있지 않을까 했지만 그렇게 되면 누적합을 구할 수 없게 돼서 다른 벡터를 하나 더 사용해야한다. 

 

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

int solution(vector<vector<int> > maps)
{
    int n = maps.size();
    int m = maps[0].size();

    queue<pair<int, int>> q;
    vector<vector<int>> graph(n, vector<int>(m, 0));
	
    //상하좌우 좌표
    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { -1,1,0,0 };

    q.push({ 0,0 });
    graph[0][0] = 1;

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
		
        //목표지점까지 가면 정답 return
        if (x == n - 1 && y == m - 1) {
            return graph[x][y];
        }

        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 && graph[nx][ny] == 0 && maps[nx][ny] == 1) {
                q.push({ nx,ny });
                graph[nx][ny] = graph[x][y] + 1;
            }
        }
    }
    return -1;
}