온풍기 안녕! (feat. 백준, 23289번)

온풍기 안녕!
https://www.acmicpc.net/problem/23289

23289번: 온풍기 안녕!

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/23289
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Heater {
	int x, y, d;
};
struct Wall {
	int x1, y1, x2, y2;
};
struct Point {
	int x, y;
};
int R, C, K, W;
int dx[4], dy[4];			// 동, 서, 북, 남
int maps[21][21];
vector<Heater> heaters;
Wall walls[401];
vector<Point> check_position;
inline bool check(const int& x1, const int& y1, const int& x2, const int& y2) {
	auto min_x = min(x1, x2), max_x = max(x1, x2), min_y = min(y1, y2), max_y = max(y1, y2);
	for (auto w = 0; w < W; ++w)
		if (walls[w].x1 == min_x && walls[w].y1 == min_y && walls[w].x2 == max_x && walls[w].y2 == max_y)
			return false;
	return true;
}
inline void working_heater(const int& x, const int& y, const int& d, int(*tmp)[21]) {
	bool visit[21][21] = { false };
	int nx, ny;
	queue<Point> q;
	if (d == 0)
		q.push(Point{ x, y + 1 }), tmp[x][y + 1] = 5;
	else if (d == 1)
		q.push(Point{ x, y - 1 }), tmp[x][y - 1] = 5;
	else if (d == 2)
		q.push(Point{ x - 1, y }), tmp[x - 1][y] = 5;
	else
		q.push(Point{ x + 1, y }), tmp[x + 1][y] = 5;
	
	while (!q.empty()) {
		auto p = q.front(); q.pop();
		if (tmp[p.x][p.y] == 1)				continue;
		// 히터가 동쪽으로
		if (d == 0) {
			// 북동쪽으로 갈수 있는지
			nx = p.x - 1, ny = p.y + 1;
			if (1 <= nx && nx <= R && 1 <= ny && ny <= C && !visit[nx][ny] && check(p.x, p.y, p.x - 1, p.y) && check(p.x - 1, p.y, p.x - 1, p.y + 1))
				visit[nx][ny] = true, tmp[nx][ny] = tmp[p.x][p.y] - 1, q.push(Point{ nx, ny });
			// 동쪽으로 갈수 있는지
			nx = p.x, ny = p.y + 1;
			if (1 <= nx && nx <= R && 1 <= ny && ny <= C && !visit[nx][ny] && check(p.x, p.y, p.x, p.y + 1))
				visit[nx][ny] = true, tmp[nx][ny] = tmp[p.x][p.y] - 1, q.push(Point{ nx, ny });
			// 남동쪽으로 갈수 있는지
			nx = p.x + 1, ny = p.y + 1;
			if (1 <= nx && nx <= R && 1 <= ny && ny <= C && !visit[nx][ny] && check(p.x, p.y, p.x + 1, p.y) && check(p.x + 1, p.y, p.x + 1, p.y + 1))
				visit[nx][ny] = true, tmp[nx][ny] = tmp[p.x][p.y] - 1, q.push(Point{ nx, ny });
		}
		// 히터가 서쪽으로
		else if (d == 1) {
			// 북서쪽으로 갈수 있는지
			nx = p.x - 1, ny = p.y - 1;
			if (1 <= nx && nx <= R && 1 <= ny && ny <= C && !visit[nx][ny] && check(p.x, p.y, p.x - 1, p.y) && check(p.x - 1, p.y, p.x - 1, p.y - 1))
				visit[nx][ny] = true, tmp[nx][ny] = tmp[p.x][p.y] - 1, q.push(Point{ nx, ny });
			// 서쪽으로 갈수 있는지
			nx = p.x, ny = p.y - 1;
			if (1 <= nx && nx <= R && 1 <= ny && ny <= C && !visit[nx][ny] && check(p.x, p.y, p.x, p.y - 1))
				visit[nx][ny] = true, tmp[nx][ny] = tmp[p.x][p.y] - 1, q.push(Point{ nx, ny });
			// 남서쪽으로 갈수 있는지
			nx = p.x + 1, ny = p.y - 1;
			if (1 <= nx && nx <= R && 1 <= ny && ny <= C && !visit[nx][ny] && check(p.x, p.y, p.x + 1, p.y) && check(p.x + 1, p.y, p.x + 1, p.y - 1))
				visit[nx][ny] = true, tmp[nx][ny] = tmp[p.x][p.y] - 1, q.push(Point{ nx, ny });
		}
		// 히터가 북쪽으로
		else if (d == 2) {
			// 북서쪽으로 갈수 있는지
			nx = p.x - 1, ny = p.y - 1;
			if (1 <= nx && nx <= R && 1 <= ny && ny <= C && !visit[nx][ny] && check(p.x, p.y, p.x, p.y - 1) && check(p.x, p.y - 1, p.x - 1, p.y - 1))
				visit[nx][ny] = true, tmp[nx][ny] = tmp[p.x][p.y] - 1, q.push(Point{ nx, ny });
			// 북쪽으로 갈수 있는지
			nx = p.x - 1, ny = p.y;
			if (1 <= nx && nx <= R && 1 <= ny && ny <= C && !visit[nx][ny] && check(p.x, p.y, p.x - 1, p.y))
				visit[nx][ny] = true, tmp[nx][ny] = tmp[p.x][p.y] - 1, q.push(Point{ nx, ny });
			// 북동쪽으로 갈수 있는지
			nx = p.x - 1, ny = p.y + 1;
			if (1 <= nx && nx <= R && 1 <= ny && ny <= C && !visit[nx][ny] && check(p.x, p.y, p.x, p.y + 1) && check(p.x, p.y + 1, p.x - 1, p.y + 1))
				visit[nx][ny] = true, tmp[nx][ny] = tmp[p.x][p.y] - 1, q.push(Point{ nx, ny });
		}
		// 히터가 남쪽으로
		else {
			// 남서쪽으로 갈수 있는지
			nx = p.x + 1, ny = p.y - 1;
			if (1 <= nx && nx <= R && 1 <= ny && ny <= C && !visit[nx][ny] && check(p.x, p.y, p.x, p.y - 1) && check(p.x, p.y - 1, p.x + 1, p.y - 1))
				visit[nx][ny] = true, tmp[nx][ny] = tmp[p.x][p.y] - 1, q.push(Point{ nx, ny });
			// 남쪽으로 갈수 있는지
			nx = p.x + 1, ny = p.y;
			if (1 <= nx && nx <= R && 1 <= ny && ny <= C && !visit[nx][ny] && check(p.x, p.y, p.x + 1, p.y))
				visit[nx][ny] = true, tmp[nx][ny] = tmp[p.x][p.y] - 1, q.push(Point{ nx, ny });
			// 남동쪽으로 갈수 있는지
			nx = p.x + 1, ny = p.y + 1;
			if (1 <= nx && nx <= R && 1 <= ny && ny <= C && !visit[nx][ny] && check(p.x, p.y, p.x, p.y + 1) && check(p.x, p.y + 1, p.x + 1, p.y + 1))
				visit[nx][ny] = true, tmp[nx][ny] = tmp[p.x][p.y] - 1, q.push(Point{ nx, ny });
		}
	}
}
inline void arrange() {
	int temp[21][21] = { 0 };
	for (int ix = 1, iy, i, nx, ny, t; ix <= R; ++ix)
		for (iy = 1; iy <= C; ++iy)
			for (i = 0; i < 4; ++i) {
				nx = ix + dx[i], ny = iy + dy[i];
				if (1 <= nx && nx <= R && 1 <= ny && ny <= C && (maps[ix][iy] - maps[nx][ny]) >= 4 && check(ix, iy, nx, ny)) {
					t = (maps[ix][iy] - maps[nx][ny]) / 4, temp[nx][ny] += t, temp[ix][iy] -= t;
				}
			}
	for (int ix = 1, iy; ix <= R; ++ix)
		for (iy = 1; iy <= C; ++iy)
			maps[ix][iy] += temp[ix][iy];
}
inline void reduce_edge() {
	for (auto ix = 1; ix <= R; ++ix) {
		if (maps[ix][1] > 0)			--maps[ix][1];
		if (maps[ix][C] > 0)			--maps[ix][C];
	}
	for (auto iy = 2; iy < C; ++iy) {
		if (maps[1][iy] > 0)			--maps[1][iy];
		if (maps[R][iy] > 0)			--maps[R][iy];
	}
}
inline void run_heater() {
	for (const auto& heater : heaters) {
		int temp[21][21] = { 0 };
		working_heater(heater.x, heater.y, heater.d, temp);
		for (int ix = 1, iy; ix <= R; ++ix)
			for (iy = 1; iy <= C; ++iy)
				maps[ix][iy] += temp[ix][iy];
	}
	arrange();
	reduce_edge();
}
inline bool check_result() {
	for (const auto& t : check_position) {
		if (maps[t.x][t.y] < K)
			return false;
	}
	return true;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(), cout.tie();
	dx[0] = 0, dx[1] = 0, dx[2] = -1, dx[3] = 1;
	dy[0] = 1, dy[1] = -1, dy[2] = 0, dy[3] = 0;
	cin >> R >> C >> K;
	for (int ix = 1, iy, d; ix <= R; ++ix)
		for (iy = 1; iy <= C; ++iy) {
			cin >> d, maps[ix][iy] = 0;
			if (1 <= d && d <= 4)			heaters.push_back(Heater{ ix, iy, d - 1 });
			else if (d == 5)				check_position.push_back(Point{ ix, iy });
		}
	cin >> W;
	for (int w = 0, x, y, t; w < W; ++w) {
		cin >> x >> y >> t;
		if (t == 0)
			walls[w].x1 = x - 1, walls[w].y1 = y, walls[w].x2 = x, walls[w].y2 = y;
		else
			walls[w].x1 = x, walls[w].y1 = y, walls[w].x2 = x, walls[w].y2 = y + 1;
	}
	auto result = 0;
	for (result = 1; result <= 100; ++result) {
		run_heater();
		if (check_result())
			break;
	}
	cout << result << endl;
	return 0;
}
// *&)*@*

1. 문제 자체는 어렵지 않으니 두가지만 기재하자면
2. 하나는, 인접한 칸끼리의 온도 검사시, 나보다 검사하려는 아이의 온도가 작을때, 특히 4도 이상 차이나는 경우에만 연산이 이뤄지면 됩니다.
3. 거의 3시간을 날려먹은 요소입니다. reduce_edge() 에서 아래쪽 for문이 2부터입니다. 이유는 1부터 반복문이 흘러가면, (1,1), (1,C), (R, 1), (R, C)가 2씩 감소하기 때문입니다.