[백준 23289] 온풍기 안녕 !

대박... 찢었다...22

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

23289번: 온풍기 안녕!

#include <cstdio>
#include <vector>
#include <cstdlib>
#include <queue>
#include <cstring>
int R, C, K;
int board[20 + 2][20 + 2];
int T[20 + 2][20 + 2];

struct _at
{
	int type;
	int x, y;
};
std::vector<_at> AC;


struct _st
{
	int x, y;
};
int wall_cnt;
std::vector<_st> Wall[20 + 2][20 + 2];	// 어떤 좌표에서 어느 방향으로 벽이 있는지 
std::vector<_st> Block_K;	// 조사 대상 칸

_st lookup[5][3] = {
	{},
	// 1우
	{{-1, 1}, {0, 1}, {1, 1}},
	// 2좌
	{{-1, -1}, {0, -1}, {1, -1}},
	// 3상
	{{-1, -1}, {-1, 0}, {-1, 1}},
	// 4하
	{ {1, -1}, {1, 0}, {1, 1}}
};


_st lookup_chk[5][3] = {	// 벽 있는지 체크할 좌표
	{},
	// 1우
	{{-1, 0}, {0, 0}, {1, 0}},
	// 2좌
	{{-1, 0}, {0, 0}, {1, 0}},
	// 3상
	{{0, -1}, {0, 0}, {0, 1}},
	// 4하
	{{0, -1}, {0, 0}, {0, 1}}
};



void input()
{
	scanf("%d %d %d", &R, &C, &K);
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			scanf("%d", &board[i][j]);
			if (board[i][j] == 5) Block_K.push_back({ i, j });
			else if (board[i][j] >= 1 && board[i][j] <= 4) AC.push_back({ board[i][j], i, j });
		}
	}
	scanf("%d", &wall_cnt);
	for (int i = 0; i < wall_cnt; i++) {
		int r = 0, c = 0, t = 0;
		scanf("%d %d %d", &r, &c, &t);
		if (t == 0) {
			Wall[r][c].push_back({ r - 1, c });
			Wall[r - 1][c].push_back({ r, c });
		}
		else if (t == 1) {
			Wall[r][c].push_back({ r, c + 1 });
			Wall[r][c + 1].push_back({ r, c });
		}
	}
}


bool chk_wall(int p, int dir, int x, int y, int nx, int ny)
{
	int ax = x + lookup[dir][p].x;
	int ay = y + lookup[dir][p].y;

	if (nx == ax && ny == ay) {
		int wx = x + lookup_chk[dir][p].x;
		int wy = y + lookup_chk[dir][p].y;
		for (_st v : Wall[wx][wy]) {
			if (p != 1) if (v.x == x && v.y == y) return true;
			if (v.x == nx && v.y == ny) return true;
		}
	}
	return false;
}




void blow_air()
{
	int tmp[20 + 2][20 + 2] = { 0, };
	std::queue<_at> Q;	// 연쇄적으로 퍼짐

	for (_at v : AC) {
		memset(tmp, 0, sizeof(tmp));
		Q = {};

		// 1우
		if (v.type == 1) {
			Q.push({ 5, v.x, v.y + 1 });
			tmp[v.x][v.y + 1] = 5;
		}
		// 2좌
		if (v.type == 2) {
			Q.push({ 5, v.x, v.y - 1 });
			tmp[v.x][v.y - 1] = 5;
		}
		// 3상
		if (v.type == 3) {
			Q.push({ 5, v.x - 1, v.y });
			tmp[v.x - 1][v.y] = 5;
		}
		// 4하
		if (v.type == 4) {
			Q.push({ 5, v.x + 1, v.y });
			tmp[v.x + 1][v.y] = 5;
		}
		

		while (!Q.empty()) {
			_at data = Q.front();
			Q.pop();

			if (data.type == 0) break;

			for (int p = 0; p < 3; p++) {
				int nk = data.type - 1;
				int nx = data.x + lookup[v.type][p].x;
				int ny = data.y + lookup[v.type][p].y;

				if (nx < 1 || nx > R || ny < 1 || ny > C) continue;
				if (chk_wall(p, v.type, data.x, data.y, nx, ny)) continue;

				Q.push({ nk, nx, ny });
				tmp[nx][ny] = nk;
			}
		}

		// 적용
		for (int i = 1; i <= R; i++) {
			for (int j = 1; j <= C; j++) {
				T[i][j] += tmp[i][j];
			}
		}
	}
}



void manage_temp()
{
	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };
	
	int tmp[20 + 2][20 + 2] = { 0, };
	int visited[20 + 2][20 + 2] = { 0, };

	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			visited[i][j] = 1;
			
			// 인접한 4칸 체크 
			for (int p = 0; p < 4; p++) {
				int nx = i + dir_x[p];
				int ny = j + dir_y[p];
				bool is_wall = false;
				// 영역 밖이면 스루 
				if (nx < 1 || nx > R || ny < 1 || ny > C) continue;
				// 이미 체크했으면 스루
				if (visited[nx][ny]) continue;

				// 인접한 두 칸 사이에 벽이 있으면 온도가 조절되지 않는다 
				if (!Wall[i][j].empty()) {
					for (int k = 0; k < Wall[i][j].size(); k++) {
						if (nx == Wall[i][j][k].x && ny == Wall[i][j][k].y) {
							is_wall = true;
							break;
						}
					}
				}
				if (is_wall == true) continue;

				int sub = abs(T[i][j] - T[nx][ny]) / 4;
				if (T[i][j] < T[nx][ny]) {
					tmp[i][j] += sub;
					tmp[nx][ny] -= sub;
				}
				else if (T[i][j] > T[nx][ny]) {
					tmp[i][j] -= sub;
					tmp[nx][ny] += sub;
				}
			}
		}
	}
	// 적용 
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			T[i][j] += tmp[i][j];
		}
	}
}



void del_temp()	// 온도가 1이상인 가장 바깥쪽 칸의 온도를 1 감소시킨다 
{
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			if (i == 1 || i == R || j == 1 || j == C) {
				if (T[i][j] >= 1) T[i][j] -= 1;
			}
		}
	}
}




bool chk_K()	// 조사하는 모든 칸의 온도가 K 이상이 되었는가
{
	int cnt = 0;
	for (_st v : Block_K) {
		if (T[v.x][v.y] >= K) cnt++;
	}
	if (cnt == Block_K.size()) return true;
	return false;
}


int simul()
{
	int choco = 0;
	while(1) {
		blow_air();
		manage_temp();
		del_temp();
		choco++;
		if (choco > 100) return 101;
		if (chk_K()) return choco;
	}
	return 0;
} 


int main()
{
	input();
	int ans = simul();
	printf("%d\n", ans);
	return 0;
}