[Programmers] 게임 맵 최단거리

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/1844

코딩테스트 연습 - 게임 맵 최단거리

전형적인 BFS 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. {0, 0}에서 시작을 하므로 큐에 {0, 0, 0}을 넣어줍니다. [좌표 Y, 좌표 X, 움직인 횟수]

2. BFS를 진행해줍니다

3. 2번 과정에서 {n - 1, m - 1}에 도착하면 움직인 횟수 + 1을 반환해주고, 도달 못할 경우 -1을 반환해줍니다.

 

	#include <iostream>
	#include <vector>
	#include <queue>
	using namespace std;
	const int MAX = 100;
	typedef struct
	{
	int y, x, cnt;
	} Player;
	typedef struct
	{
	int y, x;
	} Dir;
	Dir moveDir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
	int solution(vector<vector<int> > maps)
	{
	bool visited[MAX][MAX] = { false, };
	queue<Player> q;
	q.push({ 0, 0, 0 });
	visited[0][0] = true;
	int row = maps.size();
	int col = maps[0].size();
	while (!q.empty())
	{
	int y = q.front().y;
	int x = q.front().x;
	int cnt = q.front().cnt;
	q.pop();
	if (y == row - 1 && x == col - 1)
	{
	return cnt + 1;
	}
	for (int k = 0; k < 4; k++)
	{
	int nextY = y + moveDir[k].y;
	int nextX = x + moveDir[k].x;
	if (nextY < 0 || nextY >= row || nextX < 0 || nextX >= col)
	{
	continue;
	}
	if (maps[nextY][nextX] == 0 || visited[nextY][nextX])
	{
	continue;
	}
	visited[nextY][nextX] = true;
	q.push({ nextY, nextX, cnt + 1 });
	}
	}
	return -1;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~