백준 8972번 미친 아두이노 // C++

문제

 

요즘 종수는 아두이노를 이용해 "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초가 지나면 다음과 같은 행동이 일어난다.

• 종수의 아두이노가 움직인다.
• 미친 아두이노가 종수의 아두이노를 향해 움직인다.

 

이 때, 종수의 아두이노와 미친 아두이노가 만나게 되면 게임에 패배하게 된다.

 

미친 아두이노는 종수의 아두이노를 향해 움직이는데,

• 미친 아두이노의 좌표 > 종수 아두이노 좌표 : 아두이노 좌표 -1로 이동
• 미친 아두이노의 좌표 < 종수 아두이노 좌표 : 아두이노 좌표 +1로 이동
• 미친 아두이노의 좌표 == 종수 아두이노 좌표 : 아두이노 이동X

위와 같이 각각 X, Y좌표가 이동한다.

 

이렇게 이동 했을 때, 미친 아두이노가 같은 좌표에 두 개 이상 겹칠 경우 해당 좌표의 아두이노는 모두 사라지게 된다.

 

두 개가 겹치는지를 확인하기 위해 temp 배열을 사용하여, 각 좌표에서의 아두이노의 개수를 세주었다.

 

종수의 아두이노와 미친 아두이노가 만나게 되면 종료하며, 미친 아두이노가 겹치게 된다면 벡터에 좌표를 저장 후 마지막에 개수를 0으로 바꿔주었다.

 

---

 

코드

#include <iostream>
#include <queue>
#include <string>

using namespace std;

int dir[9][2] = {{-1,1},{0,1},{1,1},{-1,0},{0,0},{1,0},{-1,-1},{0,-1},{1,-1} };

int board[101][101]; // 빈칸 : 0, 종수 로봇 : -1, 미친 로봇 : 1이상
int R, C;

queue<pair<int, int>> robot;
int jongX, jongY;
string op;

void input();
void move();
void print();

int main() {
	input();
	move();

	return 0;
}

void input() {
	cin >> R >> C;
	
	char ch;

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> ch;

			if (ch == 'R') {
				robot.push(make_pair(j, i));
				board[i][j] = 1;
			}
			else if (ch == 'I') {
				jongX = j;
				jongY = i;
				board[i][j] = -1;
			}
			else
				board[i][j] = 0;
		}
	}

	cin >> op;
}

void move() {
	vector<pair<int, int>> boom;

	for (int i = 0; i < op.length(); i++) {
		int temp[101][101] = { 0, };

		int nextDir = op[i] - '1';

		jongX += dir[nextDir][0];
		jongY += dir[nextDir][1];

		temp[jongY][jongX] = -1;

		int qSize = robot.size();

		for (int j = 0; j < qSize; j++) {
			int curX = robot.front().first;
			int curY = robot.front().second;
			robot.pop();

			if (board[curY][curX] == 1) {
				int nextX, nextY;

				if (curX > jongX)
					nextX = curX - 1;
				else if (curX < jongX)
					nextX = curX + 1;
				else
					nextX = curX;

				if (curY > jongY)
					nextY = curY - 1;
				else if (curY < jongY)
					nextY = curY + 1;
				else
					nextY = curY;

				if (temp[nextY][nextX] == -1) {
					printf("kraj %d\n", i + 1);
					return;
				}

				temp[nextY][nextX]++;

				if (temp[nextY][nextX] == 1) {
					robot.push(make_pair(nextX, nextY));
				}
				else {
					boom.push_back(make_pair(nextX, nextY));
				}
			}
		}

		for (int j = 0; j < boom.size(); j++) {
			temp[boom[j].second][boom[j].first] = 0;
		}
		boom.clear();

		for (int j = 0; j < R; j++) {
			for (int k = 0; k < C; k++) {
				board[j][k] = temp[j][k];
			}
		}
	}

	print();
}

void print() {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (board[i][j] == 0)
				cout << '.';
			else if (board[i][j] == -1)
				cout << 'I';
			else if (board[i][j] == 1)
				cout << 'R';
		}
		cout << "\n";
	}
}