BaekJoon 1600 말이 되고픈 원숭이

Link https://www.acmicpc.net/problem/1600

소스결과 4328 KB / 112 ms

출처 Baekjoon

언어 C++17

분류 BFS

 

설명

말이 되기위한 원숭이가 자신의 능력과 말을 흉내내는 능력을 섞어 쓰면서 시작지점에서 목표 지점까지 최대한 빠르게 가는 방법을 알아내는 문제다.

 

움직일 수 있는 경우의수는 총 12가지로 현재 위치에서 인접한 위치로 움직이는 경우와 체스의 나이트처럼 움직이는 방법이다.

이 문제의 특징은 나이트처럼 움직일 수 있는 횟수가 정해져 있다는 것과 조건부에 한해서 같은 위치를 중복해서 방문할 수 있다.

말의 움직임을 흉내내서 가는 경우와 걸어서 가는 경우를 구분 해야 하기 때문에 말의 흉내를 내는 경우의 최대 값인 30번인 경우를 포함해

최대 크기인 200 by 200의 크기의 맵이 최대경우 31장이 필요하다.

또한 움직임을 계싼 하는경우 나이트처럼 움직이는 경우를 다 소모 했다면 나이트처럼 움직이는 경우를 제외 시켜야 한다.

두가지 유의점만 신경써서 문제를 풀면 정답률이 낮은 문제를 풀이 목록에 추가 가능하다.

 

알고리즘

1. 맵 상태를 받는다.

2. 방문을 나타내기위한 배열과, 중복 추가를 막기 위한 배열을 생성한다.

3. 0 ~ 3 번까지는 걸어가는 경우이므로 말의 흉내를 낸 경우는 유지한 채 이동할 수 있는 위치를 Queue에 넣는다.

4. 4 ~ 11 번까지는 말의 흉내를 낸 경우이므로 흉내를 낸 경우에 1을 추가해 이동할 수 있는 위치를 Queue에 넣는다.

5. 3 ~ 4번을 반복해 목적지에 도착 할 때 까지 반복한다.

6. 종료 여부에 따라 -1 또는 최소값을 출력한다.

 

소스코드

#include <iostream>
#include <string.h>
#include <queue>

using namespace std;

struct Monkey {
	short x;
	short y;
	short jpCount;

	Monkey() {};
	Monkey(short x, short y, short cnt) : x(x), y(y), jpCount(cnt) {};
};

const short posX[12] = { 1, 0, -1, 0 , 1, 2, 2, 1, -1, -2, -2 , -1 };
const short posY[12] = { 0, 1, 0, -1, 2, 1, -1, -2, -2, -1, 1, 2 };
const short MAX = 200;
const short MAX_STEP = 31;

int main()
{
	bool board[MAX][MAX];
	bool isVisited[MAX][MAX][MAX_STEP];
	bool isAdded[MAX][MAX][MAX_STEP];
	queue<Monkey> curQ;
	queue<Monkey> nextQ;
	bool isOver = false;
	int res = 0;

	memset(isVisited, false, sizeof(isVisited));
	memset(isAdded, false, sizeof(isAdded));

	short w, h, jmp;

	cin >> jmp >> w >> h;

	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
			cin >> board[i][j]; // 0 - false , 1 - true

	curQ.push(Monkey(0, 0, 0));
	isAdded[0][0][0] = true;

	while (!curQ.empty())
	{
		//cout << "--------" << res << "---------" << endl; For Debug
		while (!curQ.empty())
		{
			Monkey cur = curQ.front();
			curQ.pop();

			if (isVisited[cur.x][cur.y][cur.jpCount])
				continue;

			//cout << cur.x << ", " << cur.y << " - " << cur.jpCount << endl; For Debug

			if (cur.x == h - 1 && cur.y == w - 1) // 목표지점 도착시
			{
				isOver = true;
				break;
			}

			isVisited[cur.x][cur.y][cur.jpCount] = true;

			for (int i = 0; i < 12; i++)
			{
				if (i > 3 && cur.jpCount >= jmp) // 점프 제한
					break;

				int nextX = cur.x + posX[i];
				int nextY = cur.y + posY[i];

				if (0 <= nextX && nextX < h && 0 <= nextY && nextY < w && !board[nextX][nextY] && !isAdded[nextX][nextY][cur.jpCount]) // 범위, 갈 수 있는지, 이미 추가 되었는지
				{
					if (i < 4) // 인접칸 이동
					{
						isAdded[nextX][nextY][cur.jpCount] = true;
						nextQ.push(Monkey(nextX, nextY, cur.jpCount));
					}
					else // 점프
					{
						isAdded[nextX][nextY][cur.jpCount+1] = true;
						nextQ.push(Monkey(nextX, nextY, cur.jpCount + 1));
					}
				}
			}
		}

		if (!isOver) // 종료 확인
		{
			while (!nextQ.empty())
			{
				curQ.push(nextQ.front());
				nextQ.pop();
			}
		}
		else
			break;
		res++;
	}

	if (isOver)
		cout << res;
	else
		cout << -1;

	return 0;
}