[백준/BOJ] 백준 23289번 : 온풍기 안녕!

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

23289번: 온풍기 안녕!

 

온풍기 바람이 나오는 상황을 온풍기에서 첫 번째 바람이 나오고 그 바람이 해당 온풍기의 방향으로 탐색해 나아가는 것처럼 나타냈다. 그렇게 표현한 온풍기가 나오는 함수, 온도가 조절되는 함수, 온도가 1 이상인 가장 바깥쪽 칸 온도 1씩 감소 함수, 조사하는 모든 칸의 온도가 k이상이 되었는지 검사하는 함수를 나누어서 문제를 해결했다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int r, c, k;
vector<vector<int>> board(25, vector<int>(25, 0));
vector<pair<int, int>> check_area;
vector<pair<int, pair<int, int>>> warmer;
int dxdy[5][2] = { {0,0},{0,1},{0,-1},{-1,0},{1,0} };
int w;
vector<vector<int>> check_wall(25, vector<int>(25, 0));
int result = 0;

bool CheckWall(int dir, pair<int, int> here) {

	if (dir == 1) { //here 위치의 오른쪽 벽을 확인할때
		if ((check_wall[here.first][here.second] & (1 << 1)) == 0) {
			return true;
		}
	}

	else if (dir == 2) { //here 위치의 왼쪽 벽을 확인할때
		if ((check_wall[here.first][here.second - 1] & (1 << 1)) == 0) {
			return true;
		}
	}

	else if (dir == 3) { //here 위치의 위쪽 벽을 확인할때
		if ((check_wall[here.first][here.second] & (1 << 0)) == 0) {
			return true;
		}
	}

	else if (dir == 4) { //here 위치의 아래쪽 벽을 확인할때
		if ((check_wall[here.first + 1][here.second] & (1 << 0)) == 0) {
			return true;
		}
	}

	return false;
}

//온풍기에서 바람 나오기
void Warm() {

	vector<vector<int>> plus_air(25, vector<int>(25, 0));

	for (int i = 0; i < warmer.size(); i++) {
		int w_dir = warmer[i].first;
		pair<int, int> w_here = warmer[i].second;

		vector<vector<int>> here_plus_air(25, vector<int>(25, 0));
		queue<pair<int, pair<int, int>>> warm_air;

		pair<int, int> first_warm_air = make_pair(w_here.first + dxdy[w_dir][0], w_here.second + dxdy[w_dir][1]);

		here_plus_air[first_warm_air.first][first_warm_air.second] = 5;
		warm_air.push(make_pair(5, first_warm_air));

		while (!warm_air.empty()) {
			int here_temp = warm_air.front().first;
			pair<int, int> here = warm_air.front().second;
			warm_air.pop();

			if (here_temp == 0) {
				continue;
			}

			pair<int, int> there1 = make_pair(-1, -1);
			pair<int, int> there2 = make_pair(-1, -1);
			pair<int, int> there3 = make_pair(-1, -1);

			//벽 확인
			if (w_dir == 1) { //방향이 오른쪽 방향일때
				if (CheckWall(3, here) && CheckWall(1, make_pair(here.first - 1, here.second))) {
					there1 = make_pair(here.first - 1, here.second + 1);
				}
				if (CheckWall(1, here)) {
					there2 = make_pair(here.first, here.second + 1);
				}
				if (CheckWall(4, here) && CheckWall(1, make_pair(here.first + 1, here.second))) {
					there3 = make_pair(here.first + 1, here.second + 1);
				}
			}
			else if (w_dir == 2) { //방향이 왼쪽 방향일때
				if (CheckWall(3, here) && CheckWall(2, make_pair(here.first - 1, here.second))) {
					there1 = make_pair(here.first - 1, here.second - 1);
				}
				if (CheckWall(2, here)) {
					there2 = make_pair(here.first, here.second - 1);
				}
				if (CheckWall(4, here) && CheckWall(2, make_pair(here.first + 1, here.second))) {
					there3 = make_pair(here.first + 1, here.second - 1);
				}
			}
			else if (w_dir == 3) { //방향이 위쪽 방향일때
				if (CheckWall(2, here) && CheckWall(3, make_pair(here.first, here.second - 1))) {
					there1 = make_pair(here.first - 1, here.second - 1);
				}
				if (CheckWall(3, here)) {
					there2 = make_pair(here.first - 1, here.second);
				}
				if (CheckWall(1, here) && CheckWall(3, make_pair(here.first, here.second + 1))) {
					there3 = make_pair(here.first - 1, here.second + 1);
				}
			}
			else if (w_dir == 4) { //방향이 아래쪽 방향일때
				if (CheckWall(2, here) && CheckWall(4, make_pair(here.first, here.second - 1))) {
					there1 = make_pair(here.first + 1, here.second - 1);
				}
				if (CheckWall(4, here)) {
					there2 = make_pair(here.first + 1, here.second);
				}
				if (CheckWall(1, here) && CheckWall(4, make_pair(here.first, here.second + 1))) {
					there3 = make_pair(here.first + 1, here.second + 1);
				}
			}

			//there이 범위를 벗어나지 않고, 이전에 영향받지 않은 위치인지 확인
			if (there1.first >= 1 && there1.first <= r && there1.second >= 1 && there1.second <= c && here_plus_air[there1.first][there1.second] == 0) {
				here_plus_air[there1.first][there1.second] = here_temp - 1;
				warm_air.push(make_pair(here_temp - 1, there1));
			}
			if (there2.first >= 1 && there2.first <= r && there2.second >= 1 && there2.second <= c && here_plus_air[there2.first][there2.second] == 0) {
				here_plus_air[there2.first][there2.second] = here_temp - 1;
				warm_air.push(make_pair(here_temp - 1, there2));
			}
			if (there3.first >= 1 && there3.first <= r && there3.second >= 1 && there3.second <= c && here_plus_air[there3.first][there3.second] == 0) {
				here_plus_air[there3.first][there3.second] = here_temp - 1;
				warm_air.push(make_pair(here_temp - 1, there3));
			}
		}

		for (int x = 1; x <= r; x++) {
			for (int y = 1; y <= c; y++) {
				plus_air[x][y] += here_plus_air[x][y];
			}
		}
	}

	for (int x = 1; x <= r; x++) {
		for (int y = 1; y <= c; y++) {
			board[x][y] += plus_air[x][y];
		}
	}
}

//온도 조절
void TempControl() {
	vector<vector<int>> plus_air(25, vector<int>(25, 0));

	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			pair<int, int> here = make_pair(i, j);

			for (int dir = 1; dir <= 4; dir++) {
				pair<int, int> there = make_pair(here.first + dxdy[dir][0], here.second + dxdy[dir][1]);

				//there 범위 확인
				if (there.first < 1 || there.first > r || there.second < 1 || there.second > c) {
					continue;
				}

				//벽 확인
				if (!CheckWall(dir, here)) {
					continue;
				}

				if (board[here.first][here.second] > board[there.first][there.second]) {
					plus_air[here.first][here.second] -= ((board[here.first][here.second] - board[there.first][there.second]) / 4);
					plus_air[there.first][there.second] += ((board[here.first][here.second] - board[there.first][there.second]) / 4);
				}
			}
		}
	}

	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			board[i][j] += plus_air[i][j];
		}
	}
}

//온도가 1이상인 가장 바깥쪽 칸 온도 1씩 감소
void TempDown() {
	for (int i = 1; i <= r; i++) {
		if (board[i][1] >= 1) {
			board[i][1]--;
		}
		if (board[i][c] >= 1) {
			board[i][c]--;
		}
	}
	for (int j = 2; j <= c - 1; j++) {
		if (board[1][j] >= 1) {
			board[1][j]--;
		}
		if (board[r][j] >= 1) {
			board[r][j]--;
		}
	}
}

//조사하는 모든 칸의 온도가 k이상이 되었는지 검사
bool TempCheck() {

	for (int i = 0; i < check_area.size(); i++) {
		if (board[check_area[i].first][check_area[i].second] < k) {
			return false;
		}
	}

	return true;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> r >> c >> k;

	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			int input;
			cin >> input;

			if (input == 0) {
				continue;
			}

			if (input == 5) {
				check_area.push_back(make_pair(i, j));
			}

			else {
				warmer.push_back(make_pair(input, make_pair(i, j)));
			}

		}
	}

	cin >> w;

	for (int i = 0; i < w; i++) {
		int x, y, t;
		cin >> x >> y >> t;

		check_wall[x][y] |= (1 << t);
	}

	while (1) {

		if (result > 100) {
			break;
		}

		Warm();
		TempControl();
		TempDown();
		result++;

		if (TempCheck()) {
			break;
		}
	}

	cout << result;

	return 0;
}