AI 로봇청소기

BFS, Simulation

평균 : 180'

sol : 90' 18''

• 수행 시간 : 8ms
• 메모리 : 0MB

Learnings

#include <iostream>
#include <vector>
#include <utility>
#include <tuple>
#include <queue>
#include <climits>
using namespace std;

// 1-base
#define MAX_N 31
#define EMPTY 0
#define BLOCK -1

int n, k, l;
int dustGrid[MAX_N][MAX_N];
int robotGrid[MAX_N][MAX_N];

// 우, 하, 좌, 상
const int ds[4][2] = {
	{0, 1},
	{1, 0},
	{0, -1},
	{-1, 0}
};

struct Robot {
	int i;
	int j;

	Robot() {}
	Robot(int _i, int _j) :
		i(_i), j(_j) { }
};

vector<Robot> robots;

void DebugDG() {
	cout << endl << "DEBUG DUST GRID" << endl;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (dustGrid[i][j] == BLOCK) cout << "B ";
			else cout << dustGrid[i][j] << ' ';
		}
		cout << endl;
	}
	cout << "DEBUG FIN" << endl << endl;
}

void DebugRG() {
	cout << endl << "DEBUG ROBOT GRID" << endl;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (dustGrid[i][j] == BLOCK) cout << "B ";
			else cout << robotGrid[i][j] << ' ';
		}
		cout << endl;
	}
	cout << "DEBUG FIN" << endl << endl;
}

bool InGrid(int i, int j) {
	return 1 <= i && i <= n && 1 <= j && j <= n;
}

void Init() {
	cin >> n >> k >> l;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> dustGrid[i][j];
		}
	}

	robots.resize(k + 1);
	for (int i = 1; i <= k; i++) {
		int r, c;
		cin >> r >> c;
		robots[i] = Robot(r, c);
		robotGrid[r][c] = i;
	}
}

pair<int, int> GetNextPos(int i, int j) {
	if (dustGrid[i][j] > 0) return make_pair(i, j);

	// 거리, 행, 열
	tuple<int, int, int> bestPos = {INT_MAX, INT_MAX, INT_MAX};
	bool visited[MAX_N][MAX_N];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			visited[i][j] = false;
		}
	}
	// 거리, 행, 열
	queue<tuple<int, int, int>> q;
	q.push({ 0, i, j });
	visited[i][j] = true;

	while (!q.empty()) {
		int cd, ci, cj;
		tie(cd, ci, cj) = q.front();
		q.pop();

		int bd;
		tie(bd, ignore, ignore) = bestPos;
		if (bd < cd) continue;

		for (int d = 0; d < 4; d++) {
			int ni = ci + ds[d][0], nj = cj + ds[d][1];

			if (!InGrid(ni, nj)) continue;
			if (visited[ni][nj]) continue;
			if (dustGrid[ni][nj] == BLOCK) continue;
			if (robotGrid[ni][nj] != EMPTY) continue;

			visited[ni][nj] = true;
			if (dustGrid[ni][nj] == EMPTY) q.push({ cd + 1, ni, nj });
			else if (dustGrid[ni][nj] > 0) {
				tuple<int, int, int> curPos = make_tuple(cd + 1, ni, nj);
				if (curPos < bestPos) bestPos = curPos;
			}
		}
	}

	int best_i, best_j;
	tie(ignore, best_i, best_j) = bestPos;
	return make_pair(best_i, best_j);
}

void RobotsMove() {
	for (int r = 1; r <= k; r++) {
		int ci = robots[r].i, cj = robots[r].j;
		pair<int, int> nextPos = GetNextPos(ci, cj);

		if (nextPos.first == INT_MAX) continue;
		
		int ni = nextPos.first, nj = nextPos.second;
		robotGrid[ci][cj] = EMPTY;
		robotGrid[ni][nj] = r;

		robots[r].i = ni, robots[r].j = nj;
	}
}

void Clean() {
	for (int r = 1; r <= k; r++) {
		int maxDust = 0, bestDir = -1;
		int ci = robots[r].i, cj = robots[r].j;
		dustGrid[ci][cj] = (dustGrid[ci][cj] > 20 ? dustGrid[ci][cj] - 20 : EMPTY);

		for (int d = 0; d < 4; d++) {
			int curDust = 0;
			for (int cd = 0; cd < 4; cd++) {
				if (cd == (d + 2) % 4) continue;
				
				int ni = ci + ds[cd][0], nj = cj + ds[cd][1];
				if (!InGrid(ni, nj)) continue;
				if (dustGrid[ni][nj] == BLOCK) continue;
				
				// 최대 20까지만 청소 가능
				curDust += (dustGrid[ni][nj] > 20 ? 20 : dustGrid[ni][nj]);
			}
			if (curDust > maxDust) {
				maxDust = curDust;
				bestDir = d;
			}
		}

		if (bestDir == -1) continue;

		for (int d = 0; d < 4; d++) {
			if (d == (bestDir + 2) % 4) continue;

			int ni = ci + ds[d][0], nj = cj + ds[d][1];
			if (!InGrid(ni, nj)) continue;
			if (dustGrid[ni][nj] == BLOCK) continue;

			dustGrid[ni][nj] = (dustGrid[ni][nj] > 20 ? dustGrid[ni][nj] - 20 : EMPTY);
		}
	}
}

void IncreaseDust() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (dustGrid[i][j] == EMPTY || dustGrid[i][j] == BLOCK) continue;
			dustGrid[i][j] += 5;
		}
	}
}

void Diffuse() {
	int temp[MAX_N][MAX_N];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			temp[i][j] = 0;
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (dustGrid[i][j] != EMPTY) continue;

			int curDust = 0;
			for (int d = 0; d < 4; d++) {
				int ni = i + ds[d][0], nj = j + ds[d][1];

				if (!InGrid(ni, nj)) continue;
				if (dustGrid[ni][nj] == BLOCK) continue;
				
				curDust += dustGrid[ni][nj];
			}

			curDust /= 10;
			temp[i][j] = curDust;
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			dustGrid[i][j] += temp[i][j];
		}
	}
}

void PrintDust() {
	int total = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (dustGrid[i][j] == EMPTY || dustGrid[i][j] == BLOCK) continue;
			total += dustGrid[i][j];
		}
	}
	cout << total << '\n';
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	Init();

	for (int turn = 1; turn <= l; turn++) {

		RobotsMove();

		Clean();

		IncreaseDust();

		Diffuse();
		
		PrintDust();
	}

	return 0;
}