[백준 25173] 용감한 아리의 동굴 대탈출

https://www.acmicpc.net/problem/25173

25173번: 용감한 아리의 동굴 대탈출

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
int R, C;
int board[50 + 2][50 + 2];
int tmp[50 + 2][50 + 2];

struct _st
{
	int x, y;	// 위치
	int dir;	// 방향
	int active;	// 체력
	int mana;	// 공격력
};

_st ARI[1];
_st Will_Boss[1];
_st BOSS[1];

struct _qt
{
	int x, y;
	int active;
};
std::queue<_qt> Q;
int visited[50 + 2][50 + 2];

// 0상 1우 2하 3좌
int dir_x[4] = { -1, 0 ,1, 0 };
int dir_y[4] = { 0, 1, 0, -1 };


void input()
{
	scanf("%d %d", &R, &C);
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			scanf("%d", &board[i][j]);
			if (board[i][j] == 2) {
				ARI[0].x = i;
				ARI[0].y = j;
				board[i][j] = 0;
			}
			else if (board[i][j] == 3) {
				BOSS[0].x = i;
				BOSS[0].y = j;
				board[i][j] = 0;
			}
		}
	}
	scanf("%d %d %d %d", &ARI[0].active, &ARI[0].mana, &BOSS[0].active, &BOSS[0].mana);


	// get dir
	// 0상 1우 2하 3좌
	int dir = -1;
	if (ARI[0].x < BOSS[0].x && ARI[0].y == BOSS[0].y) dir = 0;
	else if (ARI[0].x == BOSS[0].x && ARI[0].y > BOSS[0].y) dir = 1;
	else if (ARI[0].x > BOSS[0].x && ARI[0].y == BOSS[0].y) dir = 2;
	else if (ARI[0].x == BOSS[0].x && ARI[0].y < BOSS[0].y) dir = 3;
	
	ARI[0].dir = BOSS[0].dir = dir;
}

void ari_attack()
{
	BOSS[0].active -= ARI[0].mana;
}

void ari_move()
{
	memset(Will_Boss, 0, sizeof(Will_Boss));

	int x = ARI[0].x;
	int y = ARI[0].y;
	int nd = ARI[0].dir;
	bool set = false;

	for (int p = 0; p < 4; p++) {
		nd = (ARI[0].dir + p > 3) ? ARI[0].dir + p - 4 : ARI[0].dir + p;
		int nx = x + dir_x[nd];
		int ny = y + dir_y[nd];
		int active = ARI[0].active - p;
		if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;
		if (board[nx][ny] == 1) continue;
		if (nx == BOSS[0].x && ny == BOSS[0].y) continue;
		ARI[0] = { nx, ny, nd, active, ARI[0].mana };
		set = true;
		break;
	}

	if (set == true) Will_Boss[0] = { x, y, nd, 0, 0 };	// 아리 이동함 
	else {
		Will_Boss[0] = { -1, -1, -1, -1, -1 };			// 아리 이동 안함 
		ARI[0] = { x, y, nd, ARI[0].active - 4, ARI[0].mana };
	}
}


void BFS(int x, int y)
{
	Q = {};
	memset(visited, 0, sizeof(visited));

	Q.push({ x, y, BOSS[0].mana });
	visited[x][y] = 1;

	while (!Q.empty()) {
		_qt data = Q.front();
		Q.pop();

		if (data.active == 0) {
			if (data.x != ARI[0].x || data.y != ARI[0].y) return;
		}

		if (data.x == ARI[0].x && data.y == ARI[0].y) {
			ARI[0].active -= data.active;
			return;
		}

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;
			if (visited[nx][ny]) continue;
			if (nx == BOSS[0].x && ny == BOSS[0].y) continue;
			if (board[nx][ny] == 1) continue;
			Q.push({ nx, ny, data.active - 1 });
			visited[nx][ny] = 1;
		}
	}
	return;
}



void boss_attack()
{
	// 석순 찾기
	int x = BOSS[0].x; 
	int y = BOSS[0].y;
	int dir = BOSS[0].dir;
	bool find = false;
	int fx = -1; int fy = -1;

	int N = 1;
	int cann = 1;	// 보스는 이미 포함

	while(1) {
		if (cann == R * C) break;
		for (int i = 1; i <= 2; i++) {
			for (int j = 1; j <= N; j++) {
				int nx = x + dir_x[dir];
				int ny = y + dir_y[dir];

				if (nx >= 0 && nx <= R - 1 && ny >= 0 && ny <= C - 1) cann++;

				if (board[nx][ny] == 1) {
					fx = nx;
					fy = ny;
					find = true;
					break;
				}
				x = nx, y = ny;
			}
			if (find == true) break;
			dir = (dir + 1) % 4;
 		}
		if (find == true) break;
		N++;
	}
	// 석순을 발견한 경우
	if (find == true) BFS(fx, fy);
	// 석순을 발견하지 못한다면 보스는 그대로 자신의 공격 차례를 마친다. 
	else return;
}

void boss_move()
{
	if (Will_Boss[0].x == -1) return;
	BOSS[0].x = Will_Boss[0].x;
	BOSS[0].y = Will_Boss[0].y;
	BOSS[0].dir = Will_Boss[0].dir;
}



bool simul()
{
	while (1) {
		ari_attack();
		// 체력확인
		if (ARI[0].active <= 0) return false;
		if (BOSS[0].active <= 0) return true;
		ari_move();

		boss_attack();
		// 체력확인
		if (ARI[0].active <= 0) return false;
		if (BOSS[0].active <= 0) return true;
		boss_move();
	}

}


int main()
{
	input();
	if (simul()) printf("VICTORY!\n");
	else printf("CAVELIFE...\n");
	return 0;
}

달팽이 사각형을 "잘"써야 하는 문제이다. 

 

내가 문제 풀면서 놓쳤던 부분은 다음과 같다. 

1. 아리가 회전할 때 마다 체력을 1 소모한다.

=> 이건 코드 다 짜고 문제 다시 읽다가 발견해서 재빨리 고쳤다. 

 

2. 달팽이 사각형을 석순 찾을 때 까지 돌려야 한다.

=> 2번 44%에서 틀리고 나서 대체 뭐가 틀린건지 몰라서 친구한테 디버깅 부탁했다. 역시나 한 번 실수했었던 달팽이 사각형... 이 문제는 달팽이 사각형을 언제까지 돌려야 한다고 정해지지 않았다. 그냥 석순을 발견하면 멈추면 된다. 그런데 석순을 발견하지 못한다면 언제까지 돌려야 할까 ? 

그리고 할당한 배열 범위 밖으로도 달팽이 사각형이 돌 수 도 있다. 

따라서 이 두 가지 조건을 모두 만족하기 위해, 달팽이 사각형을 돌면서 (nx ny)가 범위 내의 좌표라면 cann(칸 수)을 1씩 증가시켜서 R * C 배열의 모든 칸을 탐색했다면 while 루프를 종료하도록 구현했다. 

 

아이디어를 제공해준 빛빛ㄷㅇ이에게 무한감사...... ㅠ

아직도 코드를 무지성으로 짜는 것 같다. 생각좀 해야지...