[BOJ/Platinum 5] 백준 23289 온풍기 안녕!(C++)

문제 링크

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

23289번: 온풍기 안녕!

유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기

www.acmicpc.net

문제

유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)의 온도를 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

구사과의 성능 테스트는 다음과 같은 작업이 순차적으로 이루어지며, 가장 처음에 모든 칸의 온도는 0이다. 문제의 그림에서 빈 칸은 온도가 0인 칸을 의미한다.

집에 있는 모든 온풍기에서 바람이 한 번 나옴
온도가 조절됨
온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소
초콜릿을 하나 먹는다.
조사하는 모든 칸의 온도가 K 이상이 되었는지 검사. 모든 칸의 온도가 K이상이면 테스트를 중단하고, 아니면 1부터 다시 시작한다.

집에 있는 모든 온풍기에서 바람이 한 번 나오는 과정을 설명하면 다음과 같다.

<그림 1>은 크기가 7×8인 집에 온풍기가 (3, 1)에 설치되어 있는 상황이다. 온풍기는 바람이 나오는 방향이 있는데, 그 방향은 오른쪽, 왼쪽, 위, 아래 중 하나이다. 온풍기에서 따뜻한 바람이 한 번 나오면, 다음과 같은 영역의 온도가 칸에 적힌 값만큼 증가하게 된다. 아래 그림은 오른쪽 방향으로 바람이 나온 예시이며, 온풍기에서 바람이 나오는 방향에 따라 <그림 2>를 회전시켜서 해당하는 방향으로 바람이 나왔을 때 증가하는 온도를 구할 수 있다.

온풍기에서 바람이 한 번 나왔을 때, 온풍기의 바람이 나오는 방향에 있는 칸은 항상 온도가 5도 올라간다. 그 다음 이 바람은 계속 다른 칸으로 이동해 다른 칸의 온도를 위의 그림과 같이 상승시키게 된다. 어떤 칸 (x, y)에 온풍기 바람이 도착해 온도가 k (> 1)만큼 상승했다면, (x-1, y+1), (x, y+1), (x+1, y+1)의 온도도 k-1만큼 상승하게 된다. 이때 그 칸이 존재하지 않는다면, 바람은 이동하지 않는다. 온풍기에서 바람이 한 번 나왔을 때, 어떤 칸에 같은 온풍기에서 나온 바람이 여러 번 도착한다고 해도 온도는 여러번 상승하지 않는다.

<그림 1>의 상태에서 온풍기 바람이 한 번 불었다면, 증가하는 온도의 양은 <그림 3>과 같다.

일부 칸과 칸 사이에는 벽이 있어 온풍기 바람이 지나갈 수 없다. 바람이 오른쪽으로 불었을 때 어떤 칸 (x, y)에서 (x-1, y+1)로 바람이 이동할 수 있으려면, (x, y)와 (x-1, y) 사이에 벽이 없어야 하고, (x-1, y)와 (x-1, y+1) 사이에도 벽이 없어야 한다. (x, y)에서 (x, y+1)로 바람이 이동할 수 있으려면 (x, y)와 (x, y+1) 사이에 벽이 없어야 한다. 마지막으로 (x, y)에서 (x+1, y+1)로 바람이 이동할 수 있으려면, (x, y)와 (x+1, y), (x+1, y)와 (x+1, y+1) 사이에 벽이 없어야 한다.

예를 들어, (3, 4)와 (3, 5) 사이에 벽이 있는 경우 온풍기에서 바람이 한 번 나왔을 때 온도는 <그림 4>와 같이 상승한다. 벽은 빨간색으로 표시했다.

(3, 5)는 (3, 4), (2, 4), (4, 4)에서 바람이 이동할 수 없기 때문에, 온도가 상승하지 않는다.

만약 바람의 방향이 왼쪽인 온풍기가 (4, 7)에 있고, (3, 4)와 (3, 5) 사이에 벽, (2, 5)와 (3, 5) 사이에 벽이 있는 경우라면 온풍기에서 바람이 한 번 나왔을 때 <그림 5>와 같이 온도가 상승한다. <그림 6>은 바람의 방향이 아래인 온풍기가 (2, 5)에 있고, (4, 4)와 (4, 5) 사이, (4, 4)와 (5, 4) 사이, (4, 6)과 (5, 6) 사이에 벽이 있는 경우이다.

구사과의 집에는 온풍기가 2대 이상 있을 수도 있다. 이 경우 각각의 온풍기에 의해서 상승한 온도를 모두 합한 값이 해당 칸의 상승한 온도이다.

예를 들어, <그림 7>은 <그림 6>과 같은 벽을 가지고 있는 집에서 바람이 방향이 위인 온풍기가 (7, 5)에 있는 경우이고, <그림 8>는 <그림 6>과 같은 벽을 가지고 있는 집에서 바람의 방향이 아래인 온풍기가 (2, 5)에 있고, 바람의 방향이 위인 온풍기가 (7, 5)에 있는 경우이다. <그림 8>는 같은 벽을 가지고 있는 집에서 <그림 6>의 온풍기와 <그림 7>의 온풍기가 동시에 설치된 상황이기 때문에, 각 칸의 상승한 온도는 두 그림의 값을 더한 값과 같다. 온풍기가 있는 칸도 다른 온풍기에 의해 온도가 상승할 수 있기 때문에, <그림 8>에서 온풍기의 위치는 표시하지 않았다.

모든 인접한 칸에 대해서, 온도가 높은 칸에서 낮은 칸으로 ⌊(두 칸의 온도의 차이)/4⌋만큼 온도가 조절된다. 온도가 높은 칸은 이 값만큼 온도가 감소하고, 낮은 칸은 온도가 상승한다. 인접한 두 칸 사이에 벽이 있는 경우에는 온도가 조절되지 않는다. 이 과정은 모든 칸에 대해서 동시에 발생한다.온도가 조절되는 과정은 다음과 같다.

다음은 온도 조절의 예시이다.

(1, 1)에서 (1, 2)와 (1, 3)으로 공기가 섞인다.

(2, 2)와 (3, 2) 사이에 벽이 있기 때문에, (3, 2)는 온도가 그대로 유지된다.

모든 칸에 대해서 동시에 온도의 조절이 발생한다.

가장 바깥쪽 칸은 1행, R행, 1열, C열에 있는 칸이다. 예를 들어, <그림 9>와 같은 경우 가장 바깥쪽 칸의 온도가 1씩 감소하면 <그림 10>과 같이 된다. 온도가 0인 칸은 온도가 감소하지 않는다.

방의 크기와 방에 설치된 온풍기의 정보, 벽의 위치와 조사하려고 하는 칸의 위치가 주어진다. 구사과가 먹은 초콜릿의 개수를 출력한다.

입력

첫째 줄에 세 정수 R, C, K가 주어진다. 둘째 줄부터 R개의 줄에 방의 정보가 주어진다. i번째 줄의 j번째 정수는 (i, j)의 정보를 의미하며 다음 중 하나이다.

0: 빈 칸
1: 방향이 오른쪽인 온풍기가 있음
2: 방향이 왼쪽인 온풍기가 있음
3: 방향이 위인 온풍기가 있음
4: 방향이 아래인 온풍기가 있음
5: 온도를 조사해야 하는 칸

다음 줄에는 벽의 개수 W가 주어진다. 다음 W개의 줄에는 벽의 정보가 주어지며, 이 정보는 세 정수 x, y, t로 이루어져 있다. t가 0인 경우 (x, y)와 (x-1, y) 사이에 벽이 있는 것이고, 1인 경우에는 (x, y)와 (x, y+1) 사이에 벽이 있는 것이다.

출력

구사과가 먹는 초콜릿의 개수를 출력한다. 만약, 먹는 초콜릿의 개수가 100을 넘어가면 101을 출력한다.

제한

2 ≤ R, C ≤ 20
1 ≤ K ≤ 1,000
온풍기는 하나 이상 있고, 온도를 조사해야 하는 칸도 하나 이상 있다.
0 ≤ W ≤ R×C
1 < x ≤ R, 1 ≤ y ≤ C (t = 0)
1 ≤ x ≤ R, 1 ≤ y < C (t = 1)
온풍기가 있는 칸과 바람이 나오는 방향에 있는 칸 사이에는 벽이 없다.
온풍기의 바람이 나오는 방향에 있는 칸은 항상 존재한다.
같은 벽이 두 번 이상 주어지는 경우는 없다.

예제 입력 1

7 8 1
0 0 0 0 0 0 0 0
0 0 0 0 4 0 0 0
0 0 0 0 0 0 0 0
0 0 5 5 0 0 0 0
0 0 0 0 0 5 0 0
0 0 0 0 0 0 0 0
0 0 0 0 3 0 0 0
3
4 4 1
5 4 0
5 6 0

예제 출력 1

예제 입력 2

7 8 5
0 0 0 0 0 0 0 0
0 0 0 0 4 0 0 0
0 0 0 0 0 0 0 0
0 0 5 5 0 0 0 0
0 0 0 0 0 5 0 0
0 0 0 0 0 0 0 0
0 0 0 0 3 0 0 0
3
4 4 1
5 4 0
5 6 0

예제 출력 2

예제 입력 3

7 8 7
0 0 0 0 0 0 0 0
0 0 0 0 4 0 0 0
0 0 0 0 0 0 0 0
0 0 5 5 0 0 0 0
0 0 0 0 0 5 0 0
0 0 0 0 0 0 0 0
0 0 0 0 3 0 0 0
3
4 4 1
5 4 0
5 6 0

예제 출력 3

예제 입력 4

7 8 70
0 0 0 0 0 0 0 0
0 0 0 0 4 0 0 0
0 0 0 0 0 0 0 0
0 0 5 5 0 0 0 0
0 0 0 0 0 5 0 0
0 0 0 0 0 0 0 0
0 0 0 0 3 0 0 0
3
4 4 1
5 4 0
5 6 0

예제 출력 4

예제 입력 5

7 8 1000
0 0 0 0 0 0 0 0
0 0 0 0 4 0 0 0
0 0 0 0 0 0 0 0
0 0 5 5 0 0 0 0
0 0 0 0 0 5 0 0
0 0 0 0 0 0 0 0
0 0 0 0 3 0 0 0
3
4 4 1
5 4 0
5 6 0

예제 출력 5

예제 입력 6

7 8 100
0 0 0 0 0 0 0 0
5 0 0 0 4 0 0 0
0 0 0 0 0 0 0 0
0 0 5 5 0 0 0 0
0 0 0 0 0 5 0 0
5 0 0 0 0 0 5 0
0 0 0 0 3 0 0 0
0

예제 출력 6

예제 입력 7

7 8 100
0 0 0 0 0 0 5 0
5 4 4 4 4 4 4 0
0 0 0 0 0 0 0 0
0 0 5 5 0 0 0 0
0 0 0 0 0 5 0 0
5 0 0 0 0 0 5 0
0 0 0 0 3 0 0 0
3
4 4 1
5 4 0
5 6 0

예제 출력 7

예제 입력 8

7 8 1000
0 0 0 0 0 0 5 0
5 4 4 4 4 4 4 0
0 0 0 0 0 0 0 0
0 0 5 5 0 0 0 0
0 0 0 0 0 5 0 0
5 0 0 0 0 0 5 0
0 0 0 0 3 0 0 0
3
4 4 1
5 4 0
5 6 0

예제 출력 8

예제 입력 9

7 8 1000
0 0 0 0 0 0 0 0
4 4 4 4 4 4 4 4
0 0 0 0 0 5 0 0
0 0 5 5 0 0 5 0
0 0 0 0 0 5 0 0
5 0 0 0 0 0 5 0
3 3 3 3 3 3 3 3
3
4 4 1
5 4 0
5 6 0

예제 출력 9

알고리즘 분류

구현
시뮬레이션

풀이

역시나 어마무시한 난이도로 백린이들의 멘탈을 깨부수는 문제였다.

우선 2차원 배열을 3개를 선언했는데, 여기서 하나는 선언할 필요가 없었던 것 같다.

그리고 처음에는 벽의 상태를 담는 구조체를 선언하고, 구조체를 담는 벡터를 선언하여, 바람의 상태가 변화할 때 벽이 있는지의 유무를 반복문으로 찾게 했지만, 시간이 엄청 걸릴 것 같아서 3차원의 boolean 배열을 이용해서 벽의 유무를 체크해주었다.

예를 들면, 4 4 1이라면 (4, 4) 칸에서 동쪽 방향으로 벽이 있다는 뜻이고, 이는 (4, 5) 칸에서 서쪽 방향으로 벽이 있다는 것과 같기 때문에, Wall[4][4][1]과 Wall[4][5][2]를 true로 바꿔주는 식으로 벽의 정보를 입력받았다.

그리고 테스트를 구현해주었다.

1. 집에 있는 모든 온풍기에서 바람이 한 번 나옴

모든 온풍기에서 바람이 나오는데, 온풍기가 동쪽을 향한다면 우선 동쪽에 있는 칸의 온도가 5 올라가고, 바람이 퍼진 칸마다 (X-1,Y+1), (X,Y+1), (X+1,Y+1) 칸으로 온도가 1 낮은 바람이 퍼지게 하였으며, 본인은 이것을 재귀로 구현하였다. 마찬가지로 서쪽을 향한다면 (X-1,Y-1), (X,Y-1), (X+1,Y-1) 칸, 북쪽을 향한다면 (X-1,Y-1), (X-1,Y), (X-1,Y+1) 칸, 남쪽을 향한다면 (X+1,Y-1), (X+1,Y), (X+1,Y+1) 칸으로 온도가 1 낮은 바람이 퍼지게 하였다.
온풍기에서 바람이 퍼지는 과정에서는 한 칸에 한 번만 바람이 부므로, 임시 배열에 바람이 퍼지면서 이미 임시 배열의 (X,Y) 칸에 바람이 있다면(값이 0보다 크다면) 그 쪽으로는 다시 바람이 퍼지지 않는다.
온풍기 여러 대에서 같은 칸에 바람이 퍼질 수 있고, 온도 값은 더해진다고 하였으므로, 한 온풍기에서 바람이 모두 불었으면 임시 배열의 (X,Y) 칸에 있는 값을 바람의 상태 배열(Wind_MAP)의 (X,Y) 칸에 더해준다.
이 과정을 온풍기의 대수만큼 반복한다.

2. 온도가 조절됨

하나의 행에서 1~C열까지 모두 탐색을 진행하며, 행은 R개가 있으므로 이것을 R번 반복한다. 즉, 왼쪽 위 칸부터 순차적으로 온도 조절을 진행하기 때문에, 서, 북쪽 칸과의 온도 조절은 할 필요가 없다.
다시 임시 배열을 사용하여, 동, 남쪽과의 온도 차를 구하고 ⌊(온도 차)/4⌋만큼을 온도가 높은 곳은 빼고, 낮은 곳은 더해야 한다. 그런데 모든 칸에서 동시에 온도 조절이 발생한다고 하였다. 따라서, 임시 배열에 변화된 온도가 아닌 "온도의 변화량"을 입력한다.
모든 칸의 온도 조절이 끝났으면, 다시 임시 배열의 (X,Y) 칸에 있는 값을 바람의 상태 배열(Wind_MAP)의 (X,Y) 칸에 더해줌으로써 온도 조절이 완료된다.

3. 온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소

가장 바깥쪽 칸, 즉 1번째, R번째 행 전체, 1번째, C번째 열 전체의 온도가 1씩 감소하며, 온도가 이미 0이면 변화하지 않는다.

4. 초콜릿을 하나 먹는다.

초콜릿 변수를 선언하여, 초콜릿을 1 증가시켜 준다.

5. 조사하는 모든 칸의 온도가 K 이상이 되었는지 검사. 모든 칸의 온도가 K이상이면 테스트를 중단하고, 아니면 1부터 다시 시작한다.

모든 칸을 조사할 필요 없이 아까 조사해야 할 칸의 정보를 담은 Investigate 벡터 내에서 반복문을 돌려, 조사해야 할 칸의 온도만 체크해주면 된다.
하나라도 조사할 칸의 온도가 K에 미치치 못 한다면 false를 출력하여 테스트를 계속 진행한다.

주의해야 할 점은 먹은 초콜릿이 100개가 넘어가면 무조건 101이 출력되므로, 초콜릿의 개수가 100이 넘어갔다면 즉시 테스트를 종료시킨다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 25
#define LL long long
#define INF 1e9

using namespace std;
struct BLOWER {
	int Y, X, Dir;
};

int R, C, K, W;
int MAP[MAX][MAX]; // 방의 정보
int Wind_MAP[MAX][MAX]; // 바람의 상태
int Tmp_MAP[MAX][MAX]; // 바람의 변화를 담을 임시 배열
bool Wall[MAX][MAX][5]; // 벽의 유무, (i,j)의 k방향(동:1, 서:2, 북:3, 남:4)에 벽이 있으면 true, 없으면 false
vector<BLOWER> Blower; // 온풍기
vector<pair<int, int> > Investigate; // 조사할 곳
int moveY[5] = { 0,0,0,-1,1 };
int moveX[5] = { 0,1,-1,0,0 };
int answer = 0; // 먹은 초콜릿의 개수

void init() { // 임시 배열을 초기화시키는 함수
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			Tmp_MAP[i][j] = 0;
		}
	}
}

void Copy_Map() { // 바람의 가중치에 따라 바람의 상태가 변화함.
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			Wind_MAP[i][j] += Tmp_MAP[i][j];
		}
	}
}

void Make_Wind_East(int Depth, int Y, int X) {
	// 온풍기에서 바람이 동쪽으로 나올 때
	if (Depth == 0) { // 바람의 세기가 0이 되면 더 이상 바람이 퍼지지 않는다.
		return;
	}
	Tmp_MAP[Y][X] = Depth;
	int nextY = Y - 1;
	int nextX = X + 1;
	/*
		칸 (x, y)에서 (x-1, y+1)로 바람이 이동할 수 있으려면, 
		(x, y)와 (x-1, y) 사이에 벽이 없어야 하고, (x-1, y)와 (x-1, y+1) 사이에도 벽이 없어야 한다.
	*/
	if ((nextY >= 1) && (nextY <= R) && (nextX >= 1) && (nextX <= C) && (Tmp_MAP[nextY][nextX] == 0) && (!Wall[Y][X][3]) && (!Wall[Y - 1][X][1])) {
		Make_Wind_East(Depth - 1, nextY, nextX);
	}
	nextY = Y;
	nextX = X + 1;
	/*
		(x, y)에서 (x, y+1)로 바람이 이동할 수 있으려면 (x, y)와 (x, y+1) 사이에 벽이 없어야 한다. 
	*/
	if ((nextY >= 1) && (nextY <= R) && (nextX >= 1) && (nextX <= C) && (Tmp_MAP[nextY][nextX] == 0) && (!Wall[Y][X][1])) {
		Make_Wind_East(Depth - 1, nextY, nextX);
	}
	nextY = Y + 1;
	nextX = X + 1;
	/*
		(x, y)에서 (x+1, y+1)로 바람이 이동할 수 있으려면, (x, y)와 (x+1, y), (x+1, y)와 (x+1, y+1) 사이에 벽이 없어야 한다.
	*/
	if ((nextY >= 1) && (nextY <= R) && (nextX >= 1) && (nextX <= C) && (Tmp_MAP[nextY][nextX] == 0) && (!Wall[Y][X][4]) && (!Wall[Y + 1][X][1])) {
		Make_Wind_East(Depth - 1, nextY, nextX);
	}
}

void Make_Wind_West(int Depth, int Y, int X) {
	// 온풍기에서 바람이 서쪽으로 나올 때
	if (Depth == 0) {
		return;
	}
	Tmp_MAP[Y][X] = Depth;
	int nextY = Y - 1;
	int nextX = X - 1;
	/*
		칸 (x, y)에서 (x-1, y-1)로 바람이 이동할 수 있으려면,
		(x, y)와 (x-1, y) 사이에 벽이 없어야 하고, (x-1, y)와 (x-1, y-1) 사이에도 벽이 없어야 한다.
	*/
	if ((nextY >= 1) && (nextY <= R) && (nextX >= 1) && (nextX <= C) && (Tmp_MAP[nextY][nextX] == 0) && (!Wall[Y][X][3]) && (!Wall[Y - 1][X][2])) {
		Make_Wind_West(Depth - 1, nextY, nextX);
	}
	nextY = Y;
	nextX = X - 1;
	/*
		(x, y)에서 (x, y-1)로 바람이 이동할 수 있으려면 (x, y)와 (x, y-1) 사이에 벽이 없어야 한다.
	*/
	if ((nextY >= 1) && (nextY <= R) && (nextX >= 1) && (nextX <= C) && (Tmp_MAP[nextY][nextX] == 0) && (!Wall[Y][X][2])) {
		Make_Wind_West(Depth - 1, nextY, nextX);
	}
	nextY = Y + 1;
	nextX = X - 1;
	/*
		(x, y)에서 (x+1, y-1)로 바람이 이동할 수 있으려면, (x, y)와 (x+1, y), (x+1, y)와 (x+1, y-1) 사이에 벽이 없어야 한다.
	*/
	if ((nextY >= 1) && (nextY <= R) && (nextX >= 1) && (nextX <= C) && (Tmp_MAP[nextY][nextX] == 0) && (!Wall[Y][X][4]) && (!Wall[Y + 1][X][2])) {
		Make_Wind_West(Depth - 1, nextY, nextX);
	}
}

void Make_Wind_North(int Depth, int Y, int X) {
	// 온풍기에서 바람이 북쪽으로 나올 때
	if (Depth == 0) {
		return;
	}
	Tmp_MAP[Y][X] = Depth;
	int nextY = Y - 1;
	int nextX = X - 1;
	/*
		칸 (x, y)에서 (x-1, y-1)로 바람이 이동할 수 있으려면,
		(x, y)와 (x, y-1) 사이에 벽이 없어야 하고, (x, y-1)와 (x-1, y-1) 사이에도 벽이 없어야 한다.
	*/
	if ((nextY >= 1) && (nextY <= R) && (nextX >= 1) && (nextX <= C) && (Tmp_MAP[nextY][nextX] == 0) && (!Wall[Y][X][2]) && (!Wall[Y][X - 1][3])) {
		Make_Wind_North(Depth - 1, nextY, nextX);
	}
	nextY = Y - 1;
	nextX = X;
	/*
		(x, y)에서 (x-1, y)로 바람이 이동할 수 있으려면 (x, y)와 (x-1, y) 사이에 벽이 없어야 한다.
	*/
	if ((nextY >= 1) && (nextY <= R) && (nextX >= 1) && (nextX <= C) && (Tmp_MAP[nextY][nextX] == 0) && (!Wall[Y][X][3])) {
		Make_Wind_North(Depth - 1, nextY, nextX);
	}
	nextY = Y - 1;
	nextX = X + 1;
	/*
		(x, y)에서 (x-1, y+1)로 바람이 이동할 수 있으려면, (x, y)와 (x, y+1), (x, y+1)와 (x-1, y+1) 사이에 벽이 없어야 한다.
	*/
	if ((nextY >= 1) && (nextY <= R) && (nextX >= 1) && (nextX <= C) && (Tmp_MAP[nextY][nextX] == 0) && (!Wall[Y][X][1]) && (!Wall[Y][X + 1][3])) {
		Make_Wind_North(Depth - 1, nextY, nextX);
	}
}

void Make_Wind_South(int Depth, int Y, int X) {
	// 온풍기에서 바람이 남쪽으로 나올 때
	if (Depth == 0) {
		return;
	}
	Tmp_MAP[Y][X] = Depth;
	int nextY = Y + 1;
	int nextX = X - 1;
	/*
		칸 (x, y)에서 (x+1, y-1)로 바람이 이동할 수 있으려면,
		(x, y)와 (x, y-1) 사이에 벽이 없어야 하고, (x, y-1)와 (x+1, y-1) 사이에도 벽이 없어야 한다.
	*/
	if ((nextY >= 1) && (nextY <= R) && (nextX >= 1) && (nextX <= C) && (Tmp_MAP[nextY][nextX] == 0) && (!Wall[Y][X][2]) && (!Wall[Y][X - 1][4])) {
		Make_Wind_South(Depth - 1, nextY, nextX);
	}
	nextY = Y + 1;
	nextX = X;
	/*
		(x, y)에서 (x+1, y)로 바람이 이동할 수 있으려면 (x, y)와 (x+1, y) 사이에 벽이 없어야 한다.
	*/
	if ((nextY >= 1) && (nextY <= R) && (nextX >= 1) && (nextX <= C) && (Tmp_MAP[nextY][nextX] == 0) && (!Wall[Y][X][4])) {
		Make_Wind_South(Depth - 1, nextY, nextX);
	}
	nextY = Y + 1;
	nextX = X + 1;
	/*
		(x, y)에서 (x+1, y+1)로 바람이 이동할 수 있으려면, (x, y)와 (x, y+1), (x, y+1)와 (x+1, y+1) 사이에 벽이 없어야 한다.
	*/
	if ((nextY >= 1) && (nextY <= R) && (nextX >= 1) && (nextX <= C) && (Tmp_MAP[nextY][nextX] == 0) && (!Wall[Y][X][1]) && (!Wall[Y][X + 1][4])) {
		Make_Wind_South(Depth - 1, nextY, nextX);
	}
}

void Blow_Wind() {
	// 1. 집에 있는 모든 온풍기에서 바람이 한 번 나옴
	for (int i = 0; i < Blower.size(); i++) {
		init();
		int Y = Blower[i].Y;
		int X = Blower[i].X;
		int Dir = Blower[i].Dir;
		int nextY = Y + moveY[Dir];
		int nextX = X + moveX[Dir];
		// 방향에 따라 바람이 퍼지는 방향이 다르다.
		if (Dir == 1) {
			Make_Wind_East(5, nextY, nextX);
		}
		else if (Dir == 2) {
			Make_Wind_West(5, nextY, nextX);
		}
		else if (Dir == 3) {
			Make_Wind_North(5, nextY, nextX);
		}
		else if (Dir == 4) {
			Make_Wind_South(5, nextY, nextX);
		}
		Copy_Map();
	}
}

void Temperature_Control() {
	// 2. 온도가 조절됨
	init();
	// 하나의 행에서 1~C열까지 모두 탐색하고, 이것을 R번 반복하기 때문에 서, 북쪽 칸과의 온도 조절은 할 필요가 없다.
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			int CurT = Wind_MAP[i][j];
			for (int k = 1; k <= 4; k++) {
				bool Flag = false;
				if ((i + moveY[k] >= 1) && (i + moveY[k] <= R) && (j + moveX[k] >= 1) && (j + moveX[k] <= C)) {
					if (k == 1) {
						Flag = (!Wall[i][j][1] ? true : false); // 칸 (i,j)에서 동쪽에 벽이 있으면 바람이 퍼지지 않는다.
					}
					else if (k == 4) {
						Flag = (!Wall[i][j][4] ? true : false); // 칸 (i,j)에서 북쪽에 벽이 있으면 바람이 퍼지지 않는다.
					}
				}
				if (!Flag) {
					continue;
				}
				int nextT = Wind_MAP[i + moveY[k]][j + moveX[k]];
				int SubT = abs(CurT - nextT);
				SubT /= 4; // 온도가 높은 칸에서 낮은 칸으로 ⌊(두 칸의 온도의 차이) / 4⌋만큼 온도가 조절된다.
				if (CurT > nextT) {
					Tmp_MAP[i][j] -= SubT;
					Tmp_MAP[i + moveY[k]][j + moveX[k]] += SubT; // 온도의 "변화량"을 임시 배열에 담아서 나중에 한꺼번에 처리한다.
				}
				else if (CurT < nextT) {
					Tmp_MAP[i][j] += SubT;
					Tmp_MAP[i + moveY[k]][j + moveX[k]] -= SubT;
				}
			}
		}
	}
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			// 한꺼번에 처리하는 이유는 모든 칸에 대해서 동시에 발생한다고 하였기 때문이다.
			Wind_MAP[i][j] += Tmp_MAP[i][j];
		}
	}
}

void Decrease_Temperature() {
	// 3. 온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소
	// 바깥쪽 칸에 있는 온도가 1 이상인 모든 칸의 온도가 1씩 감소한다.
	for (int i = 1; i <= C; i++) {
		if (Wind_MAP[1][i] > 0) {
			Wind_MAP[1][i]--;
		}
	}
	for (int i = 1; i <= C; i++) {
		if (Wind_MAP[R][i] > 0) {
			Wind_MAP[R][i]--;
		}
	}
	for (int i = 2; i < R; i++) {
		if (Wind_MAP[i][1] > 0) {
			Wind_MAP[i][1]--;
		}
	}
	for (int i = 2; i < R; i++) {
		if (Wind_MAP[i][C] > 0) {
			Wind_MAP[i][C]--;
		}
	}
}

void Eat_Chocolate() {
	// 4. 초콜릿을 하나 먹는다.
	answer++; // 초콜릿을 먹는다.
}

bool Check_MAP() {
	// 5. 조사하는 모든 칸의 온도가 K 이상이 되었는지 검사. 모든 칸의 온도가 K이상이면 테스트를 중단하고, 아니면 1부터 다시 시작한다.
	bool Flag = true;
	for (int i = 0; i < Investigate.size(); i++) {
		int Y = Investigate[i].first;
		int X = Investigate[i].second;
		if (Wind_MAP[Y][X] < K) {
			// 하나라도 조사할 칸의 온도가 K에 미치치 못 한다면 테스트는 끝나지 않는다.
			return false;
		}
	}
	return true;
}

void Ability_Test() {
	while (1) {
		Blow_Wind();
		Temperature_Control();
		Decrease_Temperature();
		Eat_Chocolate();
		if (answer > 100) {
			// 초콜릿을 100개 넘게 먹으면, 어차피 101로 출력할 것이므로 테스트를 중단한다.
			answer = 101;
			break;
		}
		bool Flag = Check_MAP();
		if (Flag) {
			break;
		}
	};
}

int main() {
	FIRST
	cin >> R >> C >> K;
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			cin >> MAP[i][j];
			if ((MAP[i][j] >= 1) && (MAP[i][j] <= 4)) {
				Blower.push_back({ i,j,MAP[i][j] });
			}
			else if (MAP[i][j] == 5) {
				Investigate.push_back(make_pair(i, j));
			}
		}
	}
	cin >> W;
	for (int i = 0; i < W; i++) {
		int Y, X, T;
		cin >> Y >> X >> T;
		if (T == 0) {
			Wall[Y][X][3] = true;
			Wall[Y - 1][X][4] = true;
		}
		else if (T == 1) {
			Wall[Y][X][1] = true;
			Wall[Y][X + 1][2] = true;
		}
	}
	Ability_Test();
	cout << answer << "\n";

	return 0;
}

'BOJ > Platinum ~ Diamond' 카테고리의 다른 글

[BOJ/Platinum 5] 백준 2642 전개도(C++) (0)	2022.01.26
[BOJ/Platinum 4] 백준 3025 돌 던지기(C++) (0)	2022.01.26
[BOJ/Platinum 5] 백준 19541 역학 조사(C++) (0)	2022.01.25
[BOJ/Platinum 5] 백준 17470 배열 돌리기 5(C++) (0)	2022.01.24
[BOJ/Platinum 5] 백준 5373 큐빙(C++) (0)	2022.01.23

문제 링크

문제

입력

출력

제한

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

예제 입력 3

예제 출력 3

예제 입력 4

예제 출력 4

예제 입력 5

예제 출력 5

예제 입력 6

예제 출력 6

예제 입력 7

예제 출력 7

예제 입력 8

예제 출력 8

예제 입력 9

예제 출력 9

알고리즘 분류

풀이

코드

'BOJ > Platinum ~ Diamond' 카테고리의 다른 글

티스토리툴바