[백준 8972] 미친 아두이노

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

8972번: 미친 아두이노

#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
int R, C;
char board[100 + 2][100 + 2];
int jx, jy;
char CMD[100 + 2];
int end_day;
bool mad_kill;


std::vector<int> ADU[100 + 2][100 + 2];
std::vector<int> TMP[100 + 2][100 + 2];

void input()
{
	scanf("%d %d", &R, &C);
	for (int r = 0; r < R; r++) {
		scanf("%s", &board[r]);
		for (int c = 0; c < C; c++) {
			if (board[r][c] == 'I') {
				jx = r; 
				jy = c;
			}
			else if (board[r][c] == 'R') {
				ADU[r][c].push_back(1);
			}
		}
	}
	scanf("%s", &CMD);
}


void jongsu_move(char num)
{
	//dir
	int dir_x[10] = { 0, 1, 1, 1, 0, 0, 0, -1, -1, -1 };
	int dir_y[10] = { 0, -1, 0, 1, -1, 0, 1, -1, 0, 1 };

	jx += dir_x[num - '0'];
	jy += dir_y[num - '0'];
}


void mad_move()
{
	// dir
	int dir_x[8] = { 1, 1, 1, 0, 0, -1, -1, -1 };
	int dir_y[8] = { 0, 1, -1, -1, 1, 0, 1, -1 };

	// init
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			TMP[r][c].clear();
		}
	}
	mad_kill = false;

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (ADU[r][c].empty()) continue;

			// get opt dir
			int opt_min = 0x7fffffff;
			int opt_r = -1; 
			int opt_c = -1;
			for (int p = 0; p < 8; p++) {
				int nr = r + dir_x[p];
				int nc = c + dir_y[p];
			
				int dist = abs(nr - jx) + abs(nc - jy);
				if (opt_min > dist) {
					opt_min = dist;
					opt_r = nr;
					opt_c = nc;
				}
			}
			if (opt_r == jx && opt_c == jy) mad_kill = true;
			TMP[opt_r][opt_c].push_back(1);
			ADU[r][c].clear();
		}
	}
}


void mad_chk()
{
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (TMP[r][c].size() >= 2 || TMP[r][c].size() == 0) continue;
			if (TMP[r][c].size() == 1) ADU[r][c].push_back(1);
		}
	}
}



bool simulation()
{
	for (int i = 0; ; i++) {
		if (CMD[i] == '\0') break;
		jongsu_move(CMD[i]);
		if (ADU[jx][jy].size() >= 1) {
			end_day = i + 1;
			return false;
		}
		mad_move();
		if (mad_kill == true) {
			end_day = i + 1;
			return false;
		}
		mad_chk();
	}
	return true;
}

void output()
{
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (ADU[r][c].size() >= 1) printf("R");
			else if (r == jx && c == jy) printf("I");
			else printf(".");
		}
		printf("\n");
	}
}


int main()
{
	input();
	bool res = simulation();
	if (res) output();
	else printf("kraj %d\n", end_day);
	return 0;
}

아두이노의 상태를 어떤 컨테이너에 저장할지 고민되었던 문제이다. 

미친 아두이노 각각의 상태가 중요한 것이 아니기 때문에 구조체로 따로 관리해줄 필요 없다. 

또한 한 칸에 두 개 이상의 아두이노가 존재할 수 있기 때문에 배열을 쓰지 않고, 이차원 벡터에 push_back 해주고 사이즈가 2 이상인 칸에 한하여 나중에 clear 해주었다.

 

종수가 이동했는데 해당 칸에 미친 아두이노가 있는지 없는지에 대한 판단은 ADU 벡터의 (jx, jy) 칸의 사이즈가 1 이상이면 죽였다. 

미친 아두이노가 이동했는데 해당 칸에 종수가 있는지 없는지에 대한 판단은 dist를 비교하여 도출한 (opt_r, opt_c)가 (jx, jy)와 같으면 죽였다.