[BOJ/Gold 4] 백준 8972 미친 아두이노(C++)

문제 링크

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

8972번: 미친 아두이노

문제

요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. 하지만, 미친 아두이노의 움직임은 예측할 수 있다.

게임은 R×C크기의 보드 위에서 이루어지며, 아래와 같은 5가지 과정이 반복된다.

1. 먼저, 종수가 아두이노를 8가지 방향(수직,수평,대각선)으로 이동시키거나, 그 위치에 그대로 놔둔다.
2. 종수의 아두이노가 미친 아두이노가 있는 칸으로 이동한 경우에는 게임이 끝나게 되며, 종수는 게임을 지게 된다.
3. 미친 아두이노는 8가지 방향 중에서 종수의 아두이노와 가장 가까워 지는 방향으로 한 칸 이동한다. 즉, 종수의 위치를 (r1,s1), 미친 아두이노의 위치를 (r2, s2)라고 했을 때, |r1-r2| + |s1-s2|가 가장 작아지는 방향으로 이동한다.
4. 미친 아두이노가 종수의 아두이노가 있는 칸으로 이동한 경우에는 게임이 끝나게 되고, 종수는 게임을 지게 된다.
5. 2개 또는 그 이상의 미친 아두이노가 같은 칸에 있는 경우에는 큰 폭발이 일어나고, 그 칸에 있는 아두이노는 모두 파괴된다.

종수의 시작 위치, 미친 아두이노의 위치, 종수가 움직이려고 하는 방향이 주어진다. 입력으로 주어진 방향대로 종수가 움직였을 때, 보드의 상태를 구하는 프로그램을 작성하시오. 중간에 게임에서 지게된 경우에는 몇 번째 움직임에서 죽는지를 구한다.

입력

첫째 줄에 보드의 크기 R과 C가 주어진다. (1 ≤ R, C ≤ 100)

다음 R개 줄에는 C개의 문자가 주어지며, 보드의 상태이다. '.'는 빈 칸, 'R'은 미친 아두이노, 'I'는 종수의 위치를 나타낸다.

마지막 줄에는 길이가 100을 넘지않는 문자열이 주어지며, 종수가 움직이려고 하는 방향이다. 5는 그 자리에 그대로 있는 것을 나타내고, 나머지는 아래와 같은 방향을 나타낸다.

보드를 벗어나는 입력은 주어지지 않는다.

출력

중간에 게임이 끝나는 경우에는 "kraj X"를 출력한다. X는 종수가 게임이 끝나기 전 까지 이동한 횟수이다. 그 외의 경우에는 보드의 상태를 입력과 같은 형식으로 출력한다.

예제 입력 1

4 5
I....
.....
.R.R.
.....
6

예제 출력 1

.I...
.RR..
.....
.....

예제 입력 2

9 10
..........
.........R
..........
R.........
R...I.....
R.........
..........
.........R
....R.....
5558888

예제 출력 2

....I.....
....R.....
..........
..........
..........
..........
..........
..........
..........

예제 입력 3

12 8
...I....
........
........
........
........
RR......
......RR
R......R
........
........
........
...R....
66445394444162

예제 출력 3

kraj 11

알고리즘 분류

• 구현
• 시뮬레이션

풀이

아두이노들의 위치를 나타내는 구조체를 선언하고, 미친 아두이노들의 데이터를 담는 벡터를 선언한다.

그리고 종수의 아두이노의 위치와 미친 아두이노들의 위치를 각각 나타내는 MAP 배열을 선언한다.

그리고 다음을 진행한다.

1. 종수의 아두이노가 이동할 때는 다음 위치에 미친 아두이노가 존재한다면 바로 false를 return하여 게임을 종료시킨다. 그렇지 않다면 종수의 아두이노는 제대로 움직인 것이다.

2. 미친 아두이노들을 이동시키는데, 이 때 종수의 아두이노와의 거리가 가장 짧아지는 위치를 선택한다. 종수의 아두이노를 만난다면 바로 false를 return하여 게임을 종료시킨다. 그렇지 않다면 미친 아두이노를 움직인다.

3. 이제 미친 아두이노들의 위치를 나타내는 배열을 탐색해서 미친 아두이노가 2개 이상 존재하는 위치를 폭발시켜 미친 아두이노들을 다 없앤다.

4. 마지막으로 종수의 아두이노의 위치와 미친 아두이노들의 위치를 각각 나타내는 MAP 배열을 참고하여 새로 맵을 그린다.

5. 위 과정을 반복하면서 게임이 도중에 끝나게 되면 kraj X를 출력하고, 종수의 아두이노가 마지막까지 살아있다면 현재 아두이노들의 위치를 나타내는 맵을 출력한다.

 

코드

#include <iostream>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 101
#define INF 1e9

using namespace std;
struct INFO {
	int Y, X;
};

int R, C;
bool isGameWin = true;
int Game_Over;
char MAP[MAX][MAX];
int Arduino_MAP[MAX][MAX];
int Crazy_Arduino_MAP[MAX][MAX];
INFO Arduino;
vector<INFO> Crazy_Arduino;
int moveY[10] = { 0,1,1,1,0,0,0,-1,-1,-1 };
int moveX[10] = { 0,-1,0,1,-1,0,1,-1,0,1 };
string cmd;

bool Arduino_Moving(int Y, int X, int Dir) {
	/*
		1. 먼저, 종수가 아두이노를 8가지 방향(수직,수평,대각선)으로 
		이동시키거나, 그 위치에 그대로 놔둔다.
		2. 종수의 아두이노가 미친 아두이노가 있는 칸으로 이동한 경우에는 
		게임이 끝나게 되며, 종수는 게임을 지게 된다.
	*/
	int nextY = Y + moveY[Dir];
	int nextX = X + moveX[Dir];
	if ((nextY >= 0) && (nextY < R) && (nextX >= 0) && (nextX < C)) {
		if (Crazy_Arduino_MAP[nextY][nextX] > 0) {
			return false;
		}
		Arduino_MAP[Y][X] = 0;
		Arduino_MAP[nextY][nextX] = 1;
		Arduino = { nextY, nextX };
	}
	return true;
}

bool Crazy_Arduino_Moving() {
	/*
		3. 미친 아두이노는 8가지 방향 중에서 
		종수의 아두이노와 가장 가까워 지는 방향으로 한 칸 이동한다. 
		즉, 종수의 위치를 (r1,s1), 미친 아두이노의 위치를 (r2, s2)라고 했을 때, 
		|r1-r2| + |s1-s2|가 가장 작아지는 방향으로 이동한다.
		4. 미친 아두이노가 종수의 아두이노가 있는 칸으로 이동한 경우에는 
		게임이 끝나게 되고, 종수는 게임을 지게 된다.
	*/
	int Y = Arduino.Y;
	int X = Arduino.X;
	for (int i = 0; i < Crazy_Arduino.size(); i++) {
		int CurY = Crazy_Arduino[i].Y;
		int CurX = Crazy_Arduino[i].X;
		int Will_Dir = 0;
		int Final_Len = INF;
		for (int j = 1; j <= 9; j++) {
			if (j == 5) {
				continue;
			}
			int nextY = CurY + moveY[j];
			int nextX = CurX + moveX[j];
			int Len = abs(Y - nextY) + abs(X - nextX);
			if (Final_Len > Len) {
				Final_Len = Len;
				Will_Dir = j;
			}
		}
		int nextY = CurY + moveY[Will_Dir];
		int nextX = CurX + moveX[Will_Dir];
		if ((nextY >= 0) && (nextY < R) && (nextX >= 0) && (nextX < C)) {
			if (Arduino_MAP[nextY][nextX] > 0) {
				return false;
			}
			Crazy_Arduino_MAP[CurY][CurX]--;
			Crazy_Arduino_MAP[nextY][nextX]++;
			Crazy_Arduino[i] = { nextY, nextX };
		}
	}
	return true;
}

void Explosion() {
	/*
		5. 2개 또는 그 이상의 미친 아두이노가 같은 칸에 있는 경우에는 
		큰 폭발이 일어나고, 그 칸에 있는 아두이노는 모두 파괴된다.
	*/
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (Crazy_Arduino_MAP[i][j] >= 2) {
				Crazy_Arduino_MAP[i][j] = 0;
				for (int k = 0; k < Crazy_Arduino.size(); k++) {
					int CurY = Crazy_Arduino[k].Y;
					int CurX = Crazy_Arduino[k].X;
					if ((CurY == i) && (CurX == j)) {
						Crazy_Arduino.erase(Crazy_Arduino.begin() + k);
						k--;
					}
				}
			}
		}
	}
}

void Drawing_Map() {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (Arduino_MAP[i][j] == 1) {
				MAP[i][j] = 'I';
			}
			else if (Arduino_MAP[i][j] == 0) {
				MAP[i][j] = '.';
			}
		}
	}
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (Crazy_Arduino_MAP[i][j] != 0) {
				MAP[i][j] = 'R';
			}
		}
	}
}

int main() {
	FIRST
	cin >> R >> C;
	for (int i = 0; i < R; i++) {
		string S;
		cin >> S;
		for (int j = 0; j < C; j++) {
			MAP[i][j] = S[j];
			if (MAP[i][j] == 'I') {
				Arduino_MAP[i][j] = 1;
				Arduino = { i,j };
			}
			else if (S[j] == 'R') {
				Crazy_Arduino_MAP[i][j]++;
				Crazy_Arduino.push_back({ i,j });
			}
		}
	}
	cin >> cmd;
	for (int i = 0; i < cmd.size(); i++) {
		int Dir = cmd[i] - '0';
		bool Flag1 = Arduino_Moving(Arduino.Y, Arduino.X, Dir);
		if (!Flag1) {
			isGameWin = false;
			Game_Over = i + 1;
			break;
		}
		bool Flag2 = Crazy_Arduino_Moving();
		if (!Flag2) {
			isGameWin = false;
			Game_Over = i + 1;
			break;
		}
		Explosion();
		Drawing_Map();
	}
	if (isGameWin) {
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				cout << MAP[i][j];
			}
			cout << "\n";
		}
	}
	else {
		cout << "kraj " << Game_Over << "\n";
	}

	return 0;
}