냉방 시스템

Simulation, BFS

평균 : 180'

---

sol : 194' 59''

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

Learnings

• 방향 전파 BFS를 실제로 구현해볼 수 있었다.

#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <tuple>

// office 정의
#define EMPTY 0
#define OFFICE 1
#define MAX_N 21

// 방향 정의
#define LEFT 2
#define UP 3
#define RIGHT 4
#define DOWN 5
#define SKIP 10

using namespace std;

int grid[MAX_N][MAX_N];
int coolGrid[MAX_N][MAX_N];
int tempCoolGrid[MAX_N][MAX_N];
bool wallGrid[MAX_N][MAX_N][6];

bool visited[MAX_N][MAX_N];
int n, m, k;

void DebugGrid(int g[MAX_N][MAX_N], string name) {
	cout << endl << "DEBUG " << name << " GRID" << endl;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << g[i][j] << ' ';
		}
		cout << endl;
	}
	cout << "DEBUG FIN" << endl;
}

void InitVisited() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			visited[i][j] = false;
		}
	}
}

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

void Init() {
	cin >> n >> m >> k;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> grid[i][j];
		}
	}

	for (int i = 1; i <= m; i++) {
		int x, y, s;
		cin >> x >> y >> s;

		if (s == 0) s = UP;
		else if (s == 1) s = LEFT;
		wallGrid[x][y][s] = true;
	}
}

int opDir(int dir) {
	if (dir + 2 >= 6) return (dir + 2) % 6 + 2;
	else return dir + 2;
}

void WindBFS(int i, int j, int dir) {
	// 2: 좌, 3: 상, 4: 우, 5: 하
	int ds[6][2] = { {SKIP, SKIP}, {SKIP, SKIP}, { 0, -1 }, { -1, 0 }, {0, 1}, {1, 0} };
	if (dir == LEFT) {
		// 좌, 상, 하
		ds[4][0] = SKIP;
	}
	if (dir == UP) {
		// 좌, 상, 우
		ds[5][0] = SKIP;
	}
	if (dir == RIGHT) {
		// 상, 우, 하
		ds[2][0] = SKIP;
	}
	if (dir == DOWN) {
		// 좌, 우, 하
		ds[3][0] = SKIP;
	}

	int si = i + ds[dir][0], sj = j + ds[dir][1];

	InitVisited();
	queue<tuple<int, int, int>> q;
	q.push({ si, sj, 5 });
	visited[si][sj] = true;

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

		coolGrid[ci][cj] += cc;

		if (cc == 1) continue;

		for (int d = 2; d <= 5; d++) {
			if (ds[d][0] == SKIP) continue;

			if (d == dir) {
				int ni = ci + ds[d][0], nj = cj + ds[d][1], nc = cc - 1;
				if (InGrid(ni, nj) && !visited[ni][nj]) {
					// 1. 진행하려는 방향에 벽이 있으면 안됨
					if (wallGrid[ci][cj][dir] || (wallGrid[ni][nj][opDir(dir)])) continue;
					visited[ni][nj] = true;
					q.push({ ni, nj, nc });
				}
			}
			else {
				// 1. 일단 dir가 아닌 방향으로 한 칸 이동하는 것 체크
				int ni1 = ci + ds[d][0], nj1 = cj + ds[d][1];
				if (!InGrid(ni1, nj1) || wallGrid[ci][cj][d] || wallGrid[ni1][nj1][opDir(d)]) continue;

				// 2. dir 방향으로 한 칸 이동하는 것 체크
				int ni2 = ni1 + ds[dir][0], nj2 = nj1 + ds[dir][1];
				if (!InGrid(ni2, nj2) || visited[ni2][nj2] || wallGrid[ni1][nj1][dir] || wallGrid[ni2][nj2][opDir(dir)]) continue;

				visited[ni2][nj2] = true;
				q.push({ ni2, nj2, cc - 1 });
			}
		}
	}
}

void Cooling() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			// 에어컨일 경우
			if (2 <= grid[i][j] && grid[i][j] <= 5) {
				WindBFS(i, j, grid[i][j]);
			}
		}
	}
}

void InitTempCoolGrid() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			tempCoolGrid[i][j] = 0;
		}
	}
}

void AddCool() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			coolGrid[i][j] += tempCoolGrid[i][j];
			if (coolGrid[i][j] < 0) coolGrid[i][j] = 0;
		}
	}
}

void Circulate() {
	// 2: 좌, 3: 상, 4: 우, 5: 하
	int ds[6][2] = { {SKIP, SKIP}, {SKIP, SKIP}, { 0, -1 }, { -1, 0 }, {0, 1}, {1, 0} };

	InitTempCoolGrid();

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (coolGrid[i][j] > 0) {
				for (int d = LEFT; d <= DOWN; d++) {
					int ni = i + ds[d][0], nj = j + ds[d][1];
					if (InGrid(ni, nj)) {
						if (wallGrid[i][j][d] || wallGrid[ni][nj][opDir(d)]) continue;

						if (coolGrid[i][j] - coolGrid[ni][nj] >= 4) {
							int gap = ((coolGrid[i][j] - coolGrid[ni][nj]) / 4);
							tempCoolGrid[i][j] -= gap;
							tempCoolGrid[ni][nj] += gap;
						}
					}
				}
			}
		}
	}

	AddCool();
}

void Decrease() {
	for (int i = 1; i <= n; i++) {
		if (coolGrid[i][1] > 0) coolGrid[i][1]--;
		if (coolGrid[i][n] > 0) coolGrid[i][n]--;
	}

	for (int j = 2; j <= n - 1; j++) {
		if (coolGrid[1][j] > 0) coolGrid[1][j]--;
		if (coolGrid[n][j] > 0) coolGrid[n][j]--;
	}
}

bool isFin() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (grid[i][j] == OFFICE && coolGrid[i][j] < k) return false;
		}
	}

	return true;
}

int main() {
	Init();
	int minute = 0;

	while (++minute <= 100) {
		// 1. COOLING
		Cooling();

		//DebugGrid(coolGrid, "after cooling");

		// 2. CIRCULATE
		Circulate();

		//DebugGrid(coolGrid, "after circulate");

		// 3. DECREASE
		Decrease();

		//DebugGrid(coolGrid, "after Decrease");

		// 4. CHECK FIN
		if (isFin()) break;
	}

	if (minute > 100) cout << -1;
	else cout << minute;

	return 0;
}