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

 

●문제

 

●입출력

 

문제해석 :갈수있는길 1 갈수없는길 0인 2차원배열이 주어졌을때 처음 좌상단 (0,0)에서 좌하단 목적지

까지 갈수있는 최단 거리값을 return

 

푼 방법 : BFS를 사용하여 최단루트 계산

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

int solution(vector<vector<int> > maps)
{
	//0 -> 벽 / 1 -> 갈수있는길
	//start는 왼쪽상단 (1,1) 도착은 우측하단 (n,m) 도착할수없으면 -1 최소값 return
	//최단거리문제 -> bfs문제 (queue)

	//(x좌초, y좌표), 현재까지 이동한 걸음 수)
	queue < pair<pair<int, int>, int>> q;
	//visited이름의 2차원 배열 만들기 행 : maps.size() (행의갯수) , 열 : maps[0].size() (열의 갯수)
	vector<vector<bool>>visited(maps.size(), vector<bool>(maps[0].size(), false));

	//첫(0,0)은 반드시 방문한다
	visited[0][0] = true;

	//상하좌우 방향벡터 설정
	//									  상        하       좌       우
	vector<pair<int, int>>direction = { {0, -1}, {0, +1}, {-1, 0}, {1, 0} };
	
	//bfs 처음 시작점 (0,0)을 큐에 넣기 , 시작점 포함 총 이동 횟수 카운트 1
	q.push(make_pair(make_pair(0, 0), 1));

	while (!q.empty())
	{
		//FIFO구조반환 큐에서 꺼낸 한칸의 정보를 담는다
		pair<pair<int, int>, int> currentPos = q.front();
		q.pop();

		//.first -> 좌표 / .first.first -> x좌표/ .first.second -> y좌표 / .second -> 이동거리
		int x = currentPos.first.first;
		int y = currentPos.first.second;

		//걸음수 선언
		int step = currentPos.second;

		//direction방향으로 탐색
		for (pair<int, int> p : direction)
		{
			int nextX = x + p.first;
			int nextY = y + p.second;

			//범위안이고 방문하지않았으며 벽이 아닌 칸 이동 1이 이동가능 0이벽
			if(nextX >= 0 && nextX < maps[0].size()&& nextY >= 0 && nextY < maps.size()
				&&!visited[nextY][nextX] && maps[nextY][nextX] == 1)
			{
				//최소걸음수 즉 현재 위치 행과 열이 다음 위치가 마지막 목적지일때
				if (nextX == maps[0].size() - 1 && nextY == maps.size() - 1)
				{
					return step + 1;
				}

				visited[nextY][nextX] = true;
				q.push(make_pair(make_pair(nextX, nextY), step + 1));
			}
		}
	}
	//도착 못했을때 -1
	return -1;


}

 

레벨 : 2

점수 : 1