https://www.acmicpc.net/problem/1600
말이 되기위한 원숭이가 자신의 능력과 말을 흉내내는 능력을 섞어 쓰면서 시작지점에서 목표 지점까지 최대한 빠르게 가는 방법을 알아내는 문제다.
움직일 수 있는 경우의수는 총 12가지로 현재 위치에서 인접한 위치로 움직이는 경우와 체스의 나이트처럼 움직이는 방법이다.
이 문제의 특징은 나이트처럼 움직일 수 있는 횟수가 정해져 있다는 것과 조건부에 한해서 같은 위치를 중복해서 방문할 수 있다.
말의 움직임을 흉내내서 가는 경우와 걸어서 가는 경우를 구분 해야 하기 때문에 말의 흉내를 내는 경우의 최대 값인 30번인 경우를 포함해
최대 크기인 200 by 200의 크기의 맵이 최대경우 31장이 필요하다.
또한 움직임을 계싼 하는경우 나이트처럼 움직이는 경우를 다 소모 했다면 나이트처럼 움직이는 경우를 제외 시켜야 한다.
두가지 유의점만 신경써서 문제를 풀면 정답률이 낮은 문제를 풀이 목록에 추가 가능하다.
#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;
}
2019-01-19 10:30:00에 Tistory에서 작성되었습니다.