[BOJ/백준 8972/C++] 미친 아두이노

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

8972번: 미친 아두이노

 

[문제 요약]

- 게임은 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는 그 자리에 그대로 있는 것을 나타내고, 나머지는 아래와 같은 방향을 나타낸다.

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

- 시간 제한 : 1초

- 메모리 제한 : 128MB

 

[문제 풀이]

크게 어렵지 않은 구현 문제였다.

 

문제에서 주어진 조건에 따라 종수와 미친 아두이노들을 움직여주면 간단하게 풀리는 문제였다.

 

하지만 문제가 살짝 불친절한 감이 없지 않아 있었는데, 예를들어 이동명령 중 5의 경우 이동하지 않은 경우인데 이것을 이동횟수가 증가했다고 표현해야할지 말아야될지 애매한 부분들이 있다.

결론적으로는 증가시켜야 된다 5의 경우도.

 

조건 중 미친 아두이노는 종수와 가까워지는 방향으로 이동한다고 되어있는데 이 부분은 8방향을 모두 확인해서 가장 거리가 가까워지는 방향을 리턴시키는 방식으로 함수를 작성했다.

int find_direction(int c_Row, int c_Col)
{
	int dist = 987654321;
	int direction = -1;
	for (int i = 1; i <= 9; i++)
	{
		int nrow = c_Row + dy[i];
		int ncol = c_Col + dx[i];

		if (nrow < 0 || ncol < 0 || nrow >= R || ncol >= C) continue;

		if (abs(nrow - jong_row) + abs(ncol - jong_col) < dist)
		{
			dist = abs(nrow - jong_row) + abs(ncol - jong_col);
			direction = i;
		}
	}
	return direction;
}

 

그리고 미친 아두이노들 끼리 이동하다가 같은 칸에 들어가는 경우는 다음과 같이 해결했다.

• 모든 미친 아두이노들의 위치에 대해 새롭게 이동하는 좌표를 new_move_pos라는 set에 저장하고,또 다른 2차원 배열 explode에 새롭게 이동하는 위치에 값을 하나 증가시킨다.
• set을 iterator를 이용해 확인하면서 해당 위치의 explode의 값이 1 초과면 해당 위치를 빈 칸 '.'으로 바꾸고 아니면 새롭게 미친 아두이노들의 위치를 갱신 시켜준다.

bool crazy_move()
{
	vector<vector<int>> explode(R, vector<int>(C, 0));
	set<pii> new_move_pos;
	for (int i = 0; i < crazys.size(); i++)
	{
		int row = crazys[i].first; int col = crazys[i].second;

		int direction = find_direction(row, col);
		
		int nrow = row + dy[direction];
		int ncol = col + dx[direction];

		if (mp[nrow][ncol] == 'I') return false;

		new_move_pos.insert({ nrow,ncol });
		mp[row][col] = '.';
		mp[nrow][ncol] = 'R';
		explode[nrow][ncol]++;
	}

	set<pii>::iterator iter;
	vector<pii> tmp;
	for (iter = new_move_pos.begin(); iter != new_move_pos.end(); iter++)
	{
		int row = iter->first; int col = iter->second;

		if (explode[row][col] > 1)
			mp[row][col] = '.';
		else
			tmp.push_back({ row,col });
	}
	crazys.clear(); crazys = tmp;
	return true;
}

 

문제를 풀면서 까다로웠던 부분은 위의 두개의 경우 였던 것 같다.

 

나머지 조건들은 말 그대로 작성해주면 쉽게 풀리는 문제였다.

 

[소스 코드]

#include <iostream>
#include <algorithm>
#include <set>
#include <queue>
#include <vector>
#include <map>

#define INF 987654321
#define pii pair<int,int>

using namespace std;

int R, C;
int jong_row, jong_col;
int dx[10] = { 0, -1, 0, 1, -1, 0, 1, -1, 0 ,1 };
int dy[10] = { 0, 1, 1, 1, 0 ,0 ,0 , -1 ,-1, -1 };
vector<vector<char>> mp;
vector<pii> crazys;
string op;

int find_direction(int c_Row, int c_Col)
{
	int dist = 987654321;
	int direction = -1;
	for (int i = 1; i <= 9; i++)
	{
		int nrow = c_Row + dy[i];
		int ncol = c_Col + dx[i];

		if (nrow < 0 || ncol < 0 || nrow >= R || ncol >= C) continue;

		if (abs(nrow - jong_row) + abs(ncol - jong_col) < dist)
		{
			dist = abs(nrow - jong_row) + abs(ncol - jong_col);
			direction = i;
		}
	}
	return direction;
}

bool crazy_move()
{
	vector<vector<int>> explode(R, vector<int>(C, 0));
	set<pii> new_move_pos;
	for (int i = 0; i < crazys.size(); i++)
	{
		int row = crazys[i].first; int col = crazys[i].second;

		int direction = find_direction(row, col);
		
		int nrow = row + dy[direction];
		int ncol = col + dx[direction];

		if (mp[nrow][ncol] == 'I') return false;

		new_move_pos.insert({ nrow,ncol });
		mp[row][col] = '.';
		mp[nrow][ncol] = 'R';
		explode[nrow][ncol]++;
	}

	set<pii>::iterator iter;
	vector<pii> tmp;
	for (iter = new_move_pos.begin(); iter != new_move_pos.end(); iter++)
	{
		int row = iter->first; int col = iter->second;

		if (explode[row][col] > 1)
			mp[row][col] = '.';
		else
			tmp.push_back({ row,col });
	}
	crazys.clear(); crazys = tmp;
	return true;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> R >> C;
	mp.resize(R);
	for (int i = 0; i < R; i++) mp[i].resize(C);

	for (int i = 0; i < R; i++)
	{
		for (int j = 0; j < C; j++)
		{
			cin >> mp[i][j];
			if (mp[i][j] == 'R') crazys.push_back({ i,j });
			else if (mp[i][j] == 'I') { jong_row = i; jong_col = j; }
		}
	}

	cin >> op;

	int cnt = 0;
	bool flag = false;
	for (int i = 0; i < op.size(); i++)
	{
		int operation = op[i] - '0';

		int njong_row = jong_row + dy[operation];
		int njong_col = jong_col + dx[operation];

		if (mp[njong_row][njong_col] == 'R') { cnt++; flag = true; break; }
		if (operation != 5) { mp[njong_row][njong_col] = 'I'; mp[jong_row][jong_col] = '.'; } 
		jong_row = njong_row;
		jong_col = njong_col;
		cnt++;

		if (crazy_move() == false) { flag = true; break; }
	}
	if (flag) cout << "kraj "<< cnt;
	else
	{
		for (int i = 0; i < crazys.size(); i++)
			mp[crazys[i].first][crazys[i].second] = 'R';
		for (int a = 0; a < R; a++)
		{
			for (int b = 0; b < C; b++)
			{
				cout << mp[a][b];
			}
			cout << endl;
		}
	}
}

굳