(백준 c++)23289 온풍기 안녕!

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

23289번: 온풍기 안녕!

문제 설명이 길어 상당히 까다로웠다.

그러나 순서에 맞춰 차례대로 하나씩 하면 풀기 쉬울 것 같다.

 

===전역 변수===

우선 전역 변수부터 설정한다.

R, C, K는 각각 행, 열, 일정 온도를 뜻한다.

chocolate은 출력할 값이다.

dx, dy 배열은 온풍기의 바람 방향을 뜻하며, 상하좌우의 순서다.

windX, windY 배열은 바람이 이동하는 방향을 나타냈으며, 바람의 상하좌우 방향에 맞춰서 x, y 증감으로 했다.

 

벡터도 상당히 많다.

차례대로 heater는 PAIR라는 자료형을 따로 define 했으며, 온풍기의 위치 좌표와 바람 방향을 넣어준다.

PAIR 자료형은 pair<pair<int, int>, int>로 {{x 좌표, y 좌표}, 바람 방향}을 저장한다.

 

room은 온도를 확인해야 할 좌표를 저장하며, pair<int, int>로 {x 좌표, y 좌표}를 저장한다.

board는 2차원 벡터로 20 x 20의 크기로 지정한후, R과 C의 크기에 따라서 값을 저장하거나 순회할 수 있다.

마지막으로 wall는 bool 형 3차원 벡터다.

벽의 위치를 나타내는데, 3차원으로 한 이유는 한 좌표당 상하좌우 벽의 위치를 확인하기 위함이다.

 

순서대로 진행하는 것들은 모두 함수로 쪼개서 쉽게 디버깅할 수 있도록 한다.

 

===함수===

setBoard()

R x C 만큼 반복을 하며,

0 ~ 5까지의 수를 입력받는다.

입력받는 수가 0이라면 그대로 쭉 진행하고,

만약 1 ~ 4 사이의 수라면 온풍기의 좌표와 바람 방향을 heater에 저장한다.

만약 5를 받는다면 room에 현재 좌표를 저장하고, 이후에 room을 순회하면서 K 이상인지 확인한다.

 

setWalls()

W개의 벽을 입력받으며

x y t라는 변수로 저장한다.

x y는 좌표이며, t는 0 또는 1이다.

t가 0이라면 walls[x][y][3]과 walls[x][y + 1][2]를 true로 저장한다.

t가 1이라면 walls[x][y][0]과 walls[x - 1][y][1]를 true로 저장한다.

 

이 부분이 헷갈릴 수 있는 부분이다.

필자는 walls라는 3차원 벡터를 [x 좌표][y 좌표][4방] 방식으로 이용했다.

주로 상하좌우 순서로 방향을 저장하기 때문에 0 = 상, 1 = 하, 2 = 좌, 3 = 우 를 뜻한다.

 

checkRange()

매개변수로 x, y 좌표를 받는다.

이 두 좌표가 각각 R, C를 벗어나는지 확인하는 함수.

 

checkWall()

매개변수로 x, y 좌표와 바람 방향을 받는다.

walls[x][y][바람 방향]이 true라면 벽이 있다는 것으로 false를 리턴.

false라면 벽이 없기 때문에 true를 리턴한다.

 

isBlocked()

온풍기에서 바람이 나올 때 벽이 있는지 확인을 한다.

이 부분도 상당히 길지만 원리만 알면 쉽게 구현할 수 있다.

매개변수로는 현재 바람의 좌표인 x와 y. 바람이 뻗어 나가는 좌표인 nx, ny, 바람의 방향인 direct, num이라는 특별한 수를 받아온다.

 

먼저 direct에 따라서 바람이 뻗어 나가는 방향이 달라지기 때문에 switch로 분기를 잡아준다.

필자는 계속해서 0,1,2,3의 순서로 상하좌우를 이동한다.

switch 내부에서는 num이라는 수를 이용해서 벽의 유무를 확인한다.

문제의 조건 중에서 바람은 3개의 방향으로 전파된다.

 

오른쪽 바람의 방향을 예시로 들며, O 부분이 바람의 시작 부분이다.

	x
O	x
	x

O에서 x가 표시된 곳으로 3개의 방향으로 전파되기 때문에 num이라는 숫자를 이용했다.

 

num은 0 ~ 2의 범위를 가지게 되며

바람의 방향에 따라 다르게 처리하게 되지만, 1이라면 현재 위치 x, y에서 바람의 방향으로 직선에 위치한 곳이다.

 

이 논리를 가지고 분기 처리를 하며, walls를 이용해 벽의 유무를 판단한다.

 

nx, ny는 위 표에서 x의 위치를 뜻하며, 왼쪽에 벽이 있는지 확인할 때 사용하게 된다.

(위 예시에서..!! 여기도 바람의 방향에 맞게 다르게 처리해야한다.)

 

 

blowWind()

온풍기에 바람이 부는 1단계이다.

온풍기의 개수만큼 for문을 돈다.

heater에서 x, y 좌표와 바람의 방향인 direct를 가져오며,

nx, ny는 온풍기가 처음 불기 시작하는 위치이며, 5 온도를 가지게 된다.

visited는 바람이 전파될 때 이미 전파된 부분은 확인하지 않도록 하기 위한 2차원 벡터다.

q는 바람의 전파를 BFS로 진행하며, PAIR 자료형을 저장하도록 한다.

 

BFS를 진행하기 전에

board[nx][ny] += 5

visited[nx][ny] = true

로 갱신한다.

5를 += 하는 이유는 온풍기가 여러개일 수 있으며, 해당 위치에 바람이 전파될 수 있기 때문이다.

 

이후 큐에 {{nx, ny}, 4}를 넣어주고 BFS를 진행.

 

BFS.

큐에서 바람의 좌표인 wx, wy와 저장할 온도 wind를 꺼내고 pop.

이후 for문을 도는데, 전파 횟수는 총 3개다.

for문 내부에서 현재 위치인 wx, wy에서 전파될 방향을 nextX, nextY로 저장한다.

(windX, windY 배열과 direct, j를 이용)

 

조건에 따라 큐에 넣어주도록 한다.

조건은 간단하다.

1) nextX, nextY 좌표가 board 내부에 있는지 확인

2) isBlocked 함수를 이용해 벽으로 막혀있지 않는지 확인

3) nextX, nextY 좌표를 방문한 적이 없는지 확인

4) 현재 wind가 1 이상인지 확인

 

이 4가지 조건이 true라면 큐에 삽입

큐에 삽입하기 전에 board[nextX][nextY] += wind를 해준다.

+= 하는 이유는 위에서 언급한 것처럼 온풍기가 여러대일 수 있기 때문.

큐에 넣을 때는 {{nextX, nextY}, wind - 1}로 넣어주고, 이 좌표의 visited도 true로 갱신한다.

 

regulateTemperature()

온도를 조절하는 2단계다.

PAIR 자료형을 가지는 queue를 선언한다.

우선 문제의 조건이 온풍기가 동시에 작동하기 때문에 실질적인 온도 조절은 board를 모두 순회하고 가장 마지막에 해야한다.

큐에 조절할 좌표와 온도를 저장하고, 순회가 끝난 후 처리한다.

 

우선 board를 이중 for문으로 순회하자.

만약 board[i][j]가 1 이상이라면 상하좌우를 비교하여 온도를 조절할 지 판단한다.

만약 온도를 조절할 수 있는 좌표라면 큐에 넣어주는데,

큐에 넣을 조건은 3가지다.

1) 현재 좌표의 상하좌우 이동한 좌표가 board의 범위를 벗어나지 않는지 확인

2) 현재 좌표에서 상하좌우로 벽이 없는지 확인.

3) 현재 좌표의 온도가 상하좌우 좌표의 온도보다 큰 지 확인

 

이를 만족시키면 큐에 넣어주는데,

큐에 넣어주는 것은 2가지가 있다.

먼저 두 온도의 차 / 4를 diff라는 변수에 저장.

{{i, j}, -diff} 와 {{x, y}, diff}를 큐에 저장하는데,

앞에있는 것은 온도를 빼야하기 때문에 -diff를,

뒤에있는 것은 온도를 더하기 때문에 diff를 가진다.

 

이중 for문이 끝나면 queue를 비워주면서 온도를 조절하면 된다.

 

decreaseTemperature()

board의 테두리 부분의 온도를 1 감소시키는 함수인 3단계다.

테두리를 순회하면서 온도가 1 이상인 곳들은 모두 -1 한다.

 

eatChocolate()

초콜렛을 먹는다.

 

checkRoom()

room에 저장되어 있는 좌표를 순회하여 모두 K 이상인지 확인한다.

만약 하나라도 K를 넘지 않는다면 false를 리턴하여 1단계부터 다시한다.

true를 반환한다면 모든 조건을 만족했기 때문에 main의 while문에서 탈출할 수 있다.

 

main()

이 모든 과정을 차례대로 실행시킨다.

while문을 빠져나가는 조건은 2가지가 있으며,

먹은 초콜릿이 100개가 넘을 때와 checkRoom()했을 때 true를 리턴받은 경우다.

 

리턴하기 전에는 chocolate을 확인하여 100이 넘는다면 101을, 넘지 않는다면 chocolate을 출력한다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#define PAIR pair<pair<int, int>, int>

using namespace std;

int R;
int C;
int K;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int windX[4][3] = {{-1, -1, -1}, {1, 1, 1}, {-1, 0, 1}, {-1, 0, 1}};
int windY[4][3] = {{-1, 0, 1}, {-1, 0, 1}, {-1, -1, -1}, {1, 1, 1}};
int chocolate = 0;
vector<PAIR> heater;
vector<pair<int, int>> room;
vector<vector<int>> board(20, vector<int>(20, 0));
vector<vector<vector<bool>>> walls(20, vector<vector<bool>>(20, vector<bool>(4, false)));

// 보드 세팅
void setBoard() {
	cin >> R >> C >> K;
	
	for(int i = 0; i < R; i++){
		for(int j = 0; j < C; j++){
			cin >> board[i][j];
			
			if(board[i][j] > 0){
				if(board[i][j] >= 1 && board[i][j] <= 4){
					int direct;
					
					switch(board[i][j]){
						case 1:
							direct = 3;
							break;
					
						case 2:
							direct = 2;
							break;
						
						case 3:
							direct = 0;
							break;
							
						case 4:
							direct = 1;
							break;
					}
					heater.push_back({{i, j}, direct});
				} else if(board[i][j] == 5){
					room.push_back({i, j});
				}
				
				board[i][j] = 0;
			}
		}
	}
}

// 벽 세팅
void setWalls() {
	int W;
	
	cin >> W;
	
	for(int i = 0; i < W; i++){
		int x, y, t;
		
		cin >> x >> y >> t;
		
		x--;
		y--;
		
		if(t){
			walls[x][y][3] = true;
			walls[x][y + 1][2] = true;
		} else{
			walls[x][y][0] = true;
			walls[x - 1][y][1] = true;
		}
	}
}

// 배열 범위 확인
bool checkRange(int x, int y) {
	if(x >= 0 && x < R && y >= 0 && y < C){
		return true;
	}
	
	return false;
}

// 주위에 벽 여부 확인
bool checkWall(int x, int y, int direct){
	if(walls[x][y][direct]){
		return false;
	}
	
	return true;
}

// 바람 불 때 벽 있는지 확인
bool isBlocked(int x, int y, int nx, int ny, int direct, int num) {
	switch(direct){
		case 0:
			if(num == 0){
				if(walls[x][y][2] || walls[nx][ny][1]){
					return true;
				}
			} else if(num == 1){
				if(walls[x][y][0]){
					return true;
				}
			} else{
				if(walls[x][y][3] || walls[nx][ny][1]){
					return true;
				}
			}
			break;
		
		case 1:
			if(num == 0){
				if(walls[x][y][2] || walls[nx][ny][0]){
					return true;
				}
			} else if(num == 1){
				if(walls[x][y][1]){
					return true;
				}
			} else{
				if(walls[x][y][3] || walls[nx][ny][0]){
					return true;
				}
			}
			break;
		
		case 2:
			if(num == 0){
				if(walls[x][y][0] || walls[nx][ny][3]){
					return true;
				}
			} else if(num == 1){
				if(walls[x][y][2]){
					return true;
				}
			} else{
				if(walls[x][y][1] || walls[nx][ny][3]){
					return true;
				}
			}
			break;
		
		case 3:
			if(num == 0){
				if(walls[x][y][0] || walls[nx][ny][2]){
					return true;
				}
			} else if(num == 1){
				if(walls[x][y][3]){
					return true;
				}
			} else{
				if(walls[x][y][1] || walls[nx][ny][2]){
					return true;
				}
			}
			break;
	}
	
	return false;
}

// 1. 온풍기 바람 붐
void blowWind() {
	for(int i = 0; i < heater.size(); i++){
		int x = heater[i].first.first;
		int y = heater[i].first.second;
		int direct = heater[i].second;
		int nx = x + dx[direct];
		int ny = y + dy[direct];
		vector<vector<bool>> visited(R, vector<bool>(C, false));
		queue<PAIR> q;
		
		board[nx][ny] += 5;
		visited[nx][ny] = true;
		q.push({{nx, ny}, 4});
		
		while(!q.empty()){
			int wx = q.front().first.first;
			int wy = q.front().first.second;
			int wind = q.front().second;
			
			q.pop();
			
			for(int j = 0; j < 3; j++){
				int nextX = wx + windX[direct][j];
				int nextY = wy + windY[direct][j];
				
				if(checkRange(nextX, nextY) && !isBlocked(wx, wy, nextX, nextY, direct, j) && !visited[nextX][nextY] && wind > 0){
					board[nextX][nextY] += wind;
					q.push({{nextX, nextY}, wind - 1});
					visited[nextX][nextY] = true;
				}
			}
		}
	}
	
}

// 2. 온도 조절
void regulateTemperature() {
	queue<PAIR> q;
	
	for(int i = 0; i < R; i++){
		for(int j = 0; j < C; j++){
			if(board[i][j]){
				for(int k = 0; k < 4; k++){
					int x = i + dx[k];
					int y = j + dy[k];
					
					if(checkRange(x, y) && checkWall(i, j, k) && board[i][j] > board[x][y]){
						int diff = floor((board[i][j] - board[x][y]) / 4);
						
						q.push({{i, j}, -diff});
						q.push({{x, y}, diff});
					}
				}
			}
		}
	}
	
	while(!q.empty()){
		int x = q.front().first.first;
		int y = q.front().first.second;
		int diff = q.front().second;
		
		q.pop();
		
		board[x][y] += diff;
	}
}

// 3. 바깥쪽 온도 1 감소
void decreaseTemperature() {
	for(int i = 0; i < R; i++){
		if(i == 0 || i == R - 1){
			for(int j = 1; j < C - 1; j++){
				if(board[i][j] > 0){
					board[i][j]--;
				}
			}
		}
		
		if(board[i][0] > 0){
			board[i][0]--;
		}
		
		if(board[i][C - 1] > 0){
			board[i][C - 1]--;
		}
	}
}

// 4. 초콜릿 하나 먹음
void eatChocolate() {
	chocolate++;
}

// 5. 조사할 칸 K 이상인지 검사
bool checkRoom(){
	for(int i = 0; i < room.size(); i++){
		int x = room[i].first;
		int y = room[i].second;
		
		if(board[x][y] < K){
			return false;
		}
	}
	
	return true;
}

int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);
	
	setBoard();
	
	setWalls();
	
	while(1){
		blowWind();
		
		regulateTemperature();
		
		decreaseTemperature();
		
		eatChocolate();
		
		if(chocolate > 100 || checkRoom()){
			break;
		}
	}
	
	cout << (chocolate > 100 ? 101 : chocolate);
	
	return 0;
}