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

• 문제

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

프로그래머스

 

• 풀이

// 프로그래머스 - 게임 맵 최단거리 (BFS)

#include <vector>
#include <queue>

using namespace std;

int solution(vector<vector<int>> maps)
{
	// 최종 값 (최단이동거리)를 저장할 변수 
	int answer = 0;
	
	// 맵의 가로 
	int n = maps.size();
	
	// 맵의 세로 
	int m = maps[0].size();
	
	
	// BFS 작동을 위해 사용할 방문 노드, 즉 좌표를 int, int 페어로 queue에 담아줄 예정 
	queue<pair<int, int>> q;
	
	// queue에 초기 시작점인 (0, 0)을 추가해 탐색을 시작 
	q.push({0, 0});
	
	
	// 상, 하, 좌, 우에 해당하는 방향 체크를 위한 방향 벡터 선언 
	int dx = { 0, 0, -1, 1 };
	int dy = { -1, 1, 0, 0 };
	
	// queue가 텅 빌때까지, 즉 더 이상 방문할 노드가 없을 때까지 루프를 실행 
	while(!q.empty())
	{
		// 큐의 가장 앞에 있는 노드(현재 위치)의 좌표를 가져옴. 
		auto[x, y] = q.front();
		
		// 처리한 노드는 다음 위치를 사용하기 위해서 바로 큐에서 제거 
		q.pop(); 
		
		// 현재 위치에서 상하좌우 네 방향을 모두 확인하기 시작함 
		for (int i = 0; i < 4; i++)
		{
			// 현재 x, y 좌표에 체크할 방향의 벡터를 더해 다음으로 이동할 위치의 좌표를 생성 
			int newX = x + dx[i];
			int newY = y + dy[i];
			
			// 이동할 위치가 맵의 유효 범위 내에 있는지 확인하고
			if (newX < 0 || newY < 0 || newX >= n || newY >= m)
			{
                // 맵을 벗어난 경우에는  continue로 무시 
				continue;
			}
			
			// 만약 이동할 위치가 벽(0)이면 방문할 수 없으므로 무시 
			if (maps[newX][newY] != 1)
			{
				continue;
			}
			
			// 유효 범위의 좌표에 무사히 이동했으므로, 이동 거리를 1 늘려줌. 
			map[newX][newY] = maps[x][y] + 1;
			
			// 갱신된 좌표를 다시 queue에 넣어 다음 이동을 준비함. 
			q.push({newX, newY});
		}
	}
	
    // 모든 탐색이 끝난 후, 도착 지점(n - 1, m - 1)의 값을 확인함.
	// 만약 값이 여전히 1인 경우 전혀 이동하지 않았다는 뜻이므로 이동이 불가능한 맵임을 알 수 있음
	// 따라서 이 경우에는 -1을 출력하고, 아닌 경우에만 도출된 최종 이동거리를 답으로 출력함. 
	answer = map[n - 1][m - 1] == 1 ? -1 : map[n - 1][m - 1];
	return answer;
}

 

• 정리

항목	설명
문제 유형	BFS, 최단 거리 탐색
큐 사용 이유	거리 순으로 탐색하므로 최단 거리 보장
시간 복잡도	O(N×M), 최악의 경우 전체 맵 순회
탐색 방향	4방향 (상하좌우)