[Programmers] 리코쳇 로봇

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

프로그래머스

우선순위 큐를 이용한 BFS 문제였습니다.

 

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

1. 이동한 횟수가 적을수록 우선순위가 큰 우선순위 큐에 로봇의 시작점 좌표와 이동한 횟수인 0을 넣어줍니다.

2. 우선순위 큐가 빌 때까지 혹은 목표점에 도달할 때까지 상하좌우 방향으로 부딪힐 때까지 이동시키며 시뮬레이션을 돌립니다.

2.1 목표점에 도달했다면 이동한 횟수를 반환합니다.

3. 2번 과정에서 프로그램이 종료되지 않을 경우 목표점에 도달할 수 없음을 의미하므로 -1을 반환합니다.

 

	#include <string>
	#include <vector>
	#include <queue>
	#include <iostream>
	using namespace std;
	const int MAX = 100;
	typedef struct
	{
	int y, x;
	int cnt;
	} State;
	bool operator<(const State a, const State b)
	{
	return a.cnt > b.cnt;
	}
	typedef struct
	{
	int y, x;
	} Dir;
	Dir moveDir[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	int N, M;
	bool visited[MAX][MAX][4];
	bool isOutOfBounds(int y, int x)
	{
	return y < 0 || y >= N || x < 0 || x >= M;
	}
	int solution(vector<string> board) {
	priority_queue<State> pq;
	N = board.size();
	M = board[0].size();
	for (int y = 0; y < N; y++)
	{
	for (int x = 0; x < M; x++)
	{
	if (board[y][x] == 'R')
	{
	pq.push({y, x, 0});
	for (int k = 0; k < 4; k++)
	{
	visited[y][x][k] = true;
	}
	break;
	}
	}
	if (!pq.empty())
	{
	break;
	}
	}
	while (!pq.empty())
	{
	State s = pq.top();
	int y = s.y;
	int x = s.x;
	int cnt = s.cnt;
	pq.pop();
	if (board[y][x] == 'G')
	{
	return cnt;
	}
	for (int k = 0; k < 4; k++)
	{
	int tempY = y;
	int tempX = x;
	bool flag = false;
	while (true)
	{
	int nextY = tempY + moveDir[k].y;
	int nextX = tempX + moveDir[k].x;
	if (isOutOfBounds(nextY, nextX))
	{
	break;
	}
	if (board[nextY][nextX] == 'D')
	{
	break;
	}
	if (visited[nextY][nextX][k])
	{
	flag = true;
	break;
	}
	visited[nextY][nextX][k] = true;
	tempY = nextY;
	tempX = nextX;
	}
	if (flag)
	{
	continue;
	}
	if (!(tempY == y && tempX == x))
	{
	pq.push({tempY, tempX, cnt + 1});
	}
	}
	}
	return -1;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경: Programmers IDE

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