백준 - 온풍기 안녕! (23289)

1. 문제 링크

문제 링크

2. 풀이

삼성 기출 문제답게 높은 구현력을 요구하는 문제입니다.
근데 뭐 별 거 있습니까? 늘 하던대로 계획을 세우고 하나씩 구현해봅시다.

1. 필요한 자료형의 선언

int my[4] = { -1, 0, 1, 0 };
int mx[4] = { 0, 1, 0, -1 };
int rotates[2] = { 3, 1 };
int convert[4] = { 1, 3, 0, 2 };
int board[20][20][5];
int visited[20][20];
vector<tuple<int, int, int>> hotAirBlower;
vector<pair<int, int>> checks;
queue<pair<int, int>> moveQ;
queue<tuple<int, int, int>> plusQ, minusQ;

• my, mx배열
  • 임의의 좌표를 북, 동, 남, 서로 이동할 때 쓰이는 변수
• rotates배열
  • 온풍기의 열기가 퍼져나갈 때 회전을 시켜야하는데 그 때 사용됩니다.
• convert배열
  • 문제에서 인풋으로 주어지는 방향을 제 설계에 맞는 방향으로 전환합니다.
• board배열
  • board[y][x][0] ~ board[y][x][3]은
    (y, x)좌표의 북, 동, 남, 서쪽에 벽이 있는지 여부를 저장합니다.
  • board[y][x][4]는 (y, x)좌표의 열기를 저장합니다.
• visited배열
  • 온풍기를 작동시켜서 열기를 퍼뜨릴 때,
    같은 온풍기가 퍼뜨린 위치인지 체크합니다.
• hotAirBlower벡터
  • 온풍기의 좌표와 열기를 퍼뜨리는 방향을 저장합니다.
• checks벡터
  • 문제에서 확인을 요구하는 좌표를 저장합니다.
• moveQ벡터
  • 온풍기를 작동할 때 열기를 퍼뜨리는 용으로 사용됩니다.
• plusQ, minusQ벡터
  • 온풍기 작동 후, 열기들이 조절되는 과정에 사용됩니다.

2. 인풋 입력 받기

cin >> r >> c >> k;

for (int i = 0; i < r; i++) {
	for (int j = 0; j < c; j++) {
		int a;
		cin >> a;

		if (a == 0) continue;

		// 검사할 좌표
		if (a == 5) {
			checks.push_back({ i, j }); 
		}
		// 온풍기 좌표
		else {
			hotAirBlower.push_back({ i, j, convert[a - 1] });
		}
	}
}

cin >> w;

while (w--) {
	int y, x, t;
	cin >> y >> x >> t;

	y--;
	x--;

	if (t == 0) {
		board[y][x][0] = 1; // 북쪽

		if (y - 1 >= 0) board[y - 1][x][2] = 1; // 남쪽
	}
	else {
		board[y][x][1] = 1; // 동쪽

		if (x + 1 < c) board[y][x + 1][3] = 1; // 서쪽
	}
}

2. 온풍기 작동

// 온풍기 작동
for (auto p : hotAirBlower) {
	int ty, tx, d;
	tie(ty, tx, d) = p;

	ty += my[d];
	tx += mx[d];

	if (isOut(ty, tx)) continue;

	board[ty][tx][4] += 5;
	visited[ty][tx] = 1;
	moveQ.push({ ty, tx });

	for (int i = 4; i >= 1; i--) {
		int size = moveQ.size();

		while (size--) {
			int y = moveQ.front().first;
			int x = moveQ.front().second;

			moveQ.pop();

			// 시계, 반시계
			for (int rot : rotates) {
				int nd = (d + rot) % 4;
				int sy = y + my[nd];
				int sx = x + mx[nd];
				int ey = sy + my[d];
				int ex = sx + mx[d];

				// 검사할 두 좌표가 나가지 앉았고, 목표 좌표가 방문한 적 없고, 벽으로 막히지 않았을 때
				if (!isOut(sy, sx) && !isOut(ey, ex) && !visited[ey][ex] && !board[y][x][nd] && !board[sy][sx][d]) {
					board[ey][ex][4] += i;
					visited[ey][ex] = 1;
					if (i > 1) moveQ.push({ ey, ex });
				}
			}

			// 직진
			int ey = y + my[d];
			int ex = x + mx[d];

			if (!isOut(ey, ex) && !visited[ey][ex] && !board[y][x][d]) {
				board[ey][ex][4] += i;
				visited[ey][ex] = 1;
				if (i > 1) moveQ.push({ ey, ex });
			}
		}
	}

	// 방문 초기화
	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
			visited[i][j] = 0;
}

여기서 moveQ의 역할이 중요합니다.
moveQ에서 pop으로 열기가 있는 좌표를 가져오고
그 좌표로부터 대각선, 직선 방향으로 열기를 퍼뜨린 다음
열기를 퍼뜨린 좌표들을 moveQ에 또 넣으면 됩니다.
이러면 열기가 퍼지는 과정을 쉽게 구현할 수 있습니다.

3. 온도 조절

// 온도 조절
for (int i = 0; i < r; i++) {
	for (int j = 0; j < c; j++) {
		if (board[i][j][4] == 0) continue;

		int minus = 0;

		for (int dir = 0; dir < 4; dir++) {
			int ny = i + my[dir];
			int nx = j + mx[dir];

			if (isOut(ny, nx)) continue;

			if (board[i][j][dir]) continue; // 벽으로 막혀있을 때

			if (board[i][j][4] <= board[ny][nx][4]) continue; // 현재 좌표가 열기가 더 낮을 때

			int move = (board[i][j][4] - board[ny][nx][4]) / 4;

			minus += move;
			plusQ.push({ ny, nx, move });
		}

		if (minus) minusQ.push({ i, j, minus });
	}
}

while (!minusQ.empty()) {
	int y, x, minus;
	tie(y, x, minus) = minusQ.front();
	minusQ.pop();

	board[y][x][4] -= minus;
}

while (!plusQ.empty()) {
	int y, x, plus;
	tie(y, x, plus) = plusQ.front();
	plusQ.pop();

	board[y][x][4] += plus;
}

코드가 좀 길 뿐이지 별 거 없습니다.
단순히 열기가 높은 좌표에서 낮은 좌표로 옮겨갈 열기를 큐에 저장해두고
루프를 빠져나오면 큐를 순회하며 적용시키면 됩니다.

4. 가장 자리 1 감소

// 가장 자리 감소
for (int i = 0; i < c - 1; i++) board[0][i][4] = max(0, board[0][i][4] - 1);
for (int i = 0; i < r - 1; i++) board[i][c - 1][4] = max(0, board[i][c - 1][4] - 1);
for (int i = c - 1; i > 0; i--) board[r - 1][i][4] = max(0, board[r - 1][i][4] - 1);
for (int i = r - 1; i > 0; i--) board[i][0][4] = max(0, board[i][0][4] - 1);

이런 식으로 반복해서 검사 좌표의 온도가 모두 k를 넘었을 때 종료시키면 됩니다.

3. 전체 코드

#include <bits/stdc++.h>

using namespace std;

int r, c, k, w;
int my[4] = { -1, 0, 1, 0 };
int mx[4] = { 0, 1, 0, -1 };
int rotates[2] = { 3, 1 };
int convert[4] = { 1, 3, 0, 2 };
int board[20][20][5];
int visited[20][20];
vector<tuple<int, int, int>> hotAirBlower;
vector<pair<int, int>> checks;
queue<pair<int, int>> moveQ;
queue<tuple<int, int, int>> plusQ, minusQ;

bool isOut(int y, int x) {
	return y < 0 || y >= r || x < 0 || x >= c;
}

bool checkTemper() {
	for (auto p : checks) {
		int y = p.first;
		int x = p.second;

		if (board[y][x][4] < k) return false;
	}

	return true;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> r >> c >> k;

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			int a;
			cin >> a;

			if (a == 0) continue;

			// 검사할 좌표
			if (a == 5) {
				checks.push_back({ i, j }); 
			}
			// 온풍기 좌표
			else {
				hotAirBlower.push_back({ i, j, convert[a - 1] });
			}
		}
	}

	cin >> w;

	while (w--) {
		int y, x, t;
		cin >> y >> x >> t;

		y--;
		x--;

		if (t == 0) {
			board[y][x][0] = 1; // 북쪽

			if (y - 1 >= 0) board[y - 1][x][2] = 1; // 남쪽
		}
		else {
			board[y][x][1] = 1; // 동쪽

			if (x + 1 < c) board[y][x + 1][3] = 1; // 서쪽
		}
	}

	for (int t = 1; t <= 100; t++) {
		// 온풍기 작동
		for (auto p : hotAirBlower) {
			int ty, tx, d;
			tie(ty, tx, d) = p;

			ty += my[d];
			tx += mx[d];

			if (isOut(ty, tx)) continue;

			board[ty][tx][4] += 5;
			visited[ty][tx] = 1;
			moveQ.push({ ty, tx });

			for (int i = 4; i >= 1; i--) {
				int size = moveQ.size();

				while (size--) {
					int y = moveQ.front().first;
					int x = moveQ.front().second;

					moveQ.pop();

					// 시계, 반시계
					for (int rot : rotates) {
						int nd = (d + rot) % 4;
						int sy = y + my[nd];
						int sx = x + mx[nd];
						int ey = sy + my[d];
						int ex = sx + mx[d];

						// 검사할 두 좌표가 나가지 앉았고, 목표 좌표가 방문한 적 없고, 벽으로 막히지 않았을 때
						if (!isOut(sy, sx) && !isOut(ey, ex) && !visited[ey][ex] && !board[y][x][nd] && !board[sy][sx][d]) {
							board[ey][ex][4] += i;
							visited[ey][ex] = 1;
							if (i > 1) moveQ.push({ ey, ex });
						}
					}

					// 직진
					int ey = y + my[d];
					int ex = x + mx[d];

					if (!isOut(ey, ex) && !visited[ey][ex] && !board[y][x][d]) {
						board[ey][ex][4] += i;
						visited[ey][ex] = 1;
						if (i > 1) moveQ.push({ ey, ex });
					}
				}
			}

			// 방문 초기화
			for (int i = 0; i < r; i++)
				for (int j = 0; j < c; j++)
					visited[i][j] = 0;
		}

		// 온도 조절
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				if (board[i][j][4] == 0) continue;

				int minus = 0;

				for (int dir = 0; dir < 4; dir++) {
					int ny = i + my[dir];
					int nx = j + mx[dir];

					if (isOut(ny, nx)) continue;

					if (board[i][j][dir]) continue;

					if (board[i][j][4] <= board[ny][nx][4]) continue;

					int move = (board[i][j][4] - board[ny][nx][4]) / 4;

					minus += move;
					plusQ.push({ ny, nx, move });
				}

				if (minus) minusQ.push({ i, j, minus });
			}
		}

		while (!minusQ.empty()) {
			int y, x, minus;
			tie(y, x, minus) = minusQ.front();
			minusQ.pop();

			board[y][x][4] -= minus;
		}

		while (!plusQ.empty()) {
			int y, x, plus;
			tie(y, x, plus) = plusQ.front();
			plusQ.pop();

			board[y][x][4] += plus;
		}

		// 가장 자리 감소
		for (int i = 0; i < c - 1; i++) board[0][i][4] = max(0, board[0][i][4] - 1);
		for (int i = 0; i < r - 1; i++) board[i][c - 1][4] = max(0, board[i][c - 1][4] - 1);
		for (int i = c - 1; i > 0; i--) board[r - 1][i][4] = max(0, board[r - 1][i][4] - 1);
		for (int i = r - 1; i > 0; i--) board[i][0][4] = max(0, board[i][0][4] - 1);

		// 검사
		if (checkTemper()) {
			cout << t;
			return 0;
		}
	}

	cout << 101;

	return 0;
}