<Baekjoon> #23289 Simulation_온풍기 안녕! c++

15764 단어 simulation baekjoon algorithm "삼성SW""삼성SW"

(문제를 푸는데 모든 코드를 참고했다.. 진짜 어렵다)

`🌡️1. Input`

{동,서,남,북}의 방향을 {0,1,2,3} 으로 설정한다
입력 받아야 하는 값에는 온풍기의 좌표와 방향, 벽의 좌표와 벽이 세워진 방향, 온도를 조사해야하는 좌표가 있다
온도를 조사해야하는 좌표는 vector<pair<int, int>>,
온풍기와 벽은 vector<pair<pair<int, int>, int>>으로 나타낸다
벽을 위한 맵을 하나 더 만든다. 방향은 4가지가 존재한다.
bool wallMap[][][4] 에서 wallMap[y][x][0]=true 라는뜻은 y,x에서 동쪽(0)방향으로 벽이 있다는 뜻이다.
map[][]에 입력을 받고 map[][]=0으로 만들어준다. 그 이유는 온풍기와 조사해야할 좌표는 따로 저장해두었고 map에는 온풍기에서 퍼져나오는 온도만 저장할 것이다

const int dy[] = { 0,0,1,-1 };
const int dx[] = { 1,-1,0,0 };

int R, C, K, W;

vector <pair<int, int>> pos;
vector <pair<pair<int, int>, int>> wall, heater;

vector<vector<int>> map;
bool wallMap[MAX][MAX][4];

void input() {
	cin >> R >> C >> K;

	map = vector<vector<int>>(R + 1, vector<int>(C + 1));

	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			cin >> map[i][j];
			if (map[i][j] != 0 && map[i][j] != 5)
				heater.push_back(make_pair(make_pair(i, j), map[i][j]));
			else if (map[i][j] == 5)
				pos.push_back(make_pair(i, j));
			map[i][j] = 0;
		}
	}
	cin >> W;
	for (int i = 0; i < W; i++) {
		int a, b, c; cin >> a >> b >> c;
		wall.push_back(make_pair(make_pair(a, b), c));
	}
	
}

void setting_wall() {
	for (int i = 0; i < W; i++) {
		int y = wall[i].first.first;
		int x = wall[i].first.second;
		int t = wall[i].second;

		/*
		t==0 : (y,x)기준으로 북(3)쪽에 벽
		t==1 : (y,x)기준으로 동(0)쪽에 벽
		*/
		if (t == 0) {
			wallMap[y][x][3] = true;
			wallMap[y - 1][x][2] = true;
		}
		else if (t == 1) {
			wallMap[y][x][0] = true;
			wallMap[y][x + 1][1] = true;
		}
	}
}

`🌡️2. Spread`

온풍기의 바람이 퍼지는 방향에 대해 살펴보면
우선 온풍기는 세 방향으로 퍼지는데 온풍기의 방향 (동,서,남,북)에 따라 퍼지는 좌표가 달라지기 때문에 이를 정의해준다

const int wdy[4][3] = { {-1,0,1}, {-1,0,1}, {1,1,1}, {-1, - 1, - 1}};
const int wdx[4][3] = { {1,1,1}, {-1,-1,-1}, {-1,0,1}, {-1,0,1} };

다음 중복되는 좌표를 관리할 2차원 배열 bool update[][]를 만들어준다
온풍기가 퍼지는 방식은 queue를 사용하여 관리하는데 queue에는 온풍기의 바람이 퍼질 좌표, 온도를 넣어 관리한다
동서남북의 방향을 0,1,2,3 순서대로 저장했지만 문제에서는 1,2,4,3 순으로 나타냈기 때문에 방향을 변환해준다 (change_dir 함수 사용)

void spread(int y, int x, int d) {
	bool update[MAX][MAX] = { false, };

	//처음 온풍기 위치에서 온풍기 방향으로 1칸 이동
    
	d = change_dir(d);
	y += dy[d];
	x += dx[d];

	if (y <= 0 || x <= 0 || y > R || x > C) return;

	// (y,x)좌표, 온도
	queue <pair<pair<int, int>, int>> q;
	q.push(make_pair(make_pair(y, x), 5));

	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int wind = q.front().second;

		q.pop();

		map[y][x] += wind;
		if (wind == 1) continue;

		for (int i = 0; i < 3; i++) {
			int ny = y + wdy[d][i];
			int nx = x + wdx[d][i];

			if (ny <= 0 || nx <= 0 || ny > R || nx > C) continue;

			if (update[ny][nx]==false && check_wall(y, x, d, i) == true) {
				update[ny][nx] = true;
				q.push(make_pair(make_pair(ny, nx), wind - 1));
			}
		}
	}
}

void spread_wind() {
	for (int i = 0; i < heater.size(); i++) {
		int y = heater[i].first.first;
		int x = heater[i].first.second;
		int d = heater[i].second;

		spread(y, x, d);
	}
}

여기서 바람이 세 방향으로 퍼질 때, 이미 방문되었는지 뿐만 아니라 벽이 있는지 판단하고 바람이 퍼질수 있는지 확인해야한다.
그 부분이 check_wall(y,x,d,i)
처음 호출될 때 각 좌표가 의미하는 바는 다음과 같다
이 부분은 문제에서 주어진 다음 조건에 따라 코드를 작성한다

bool check_wall(int y, int x, int d, int i) {

	// (y,x)에서 현재 방향 d로 벽이 없다면 이동 가능
	if (i == 1) {
		if (wallMap[y][x][d]==false) return true;
	}

	// 0=동, 1=서, 2=남, 3=북
	else if (i == 0) {
		if (d == 0) {
			if (wallMap[y][x][3]==false && wallMap[y - 1][x][0]==false) return true;
		}
		else if (d == 1) {
			if (wallMap[y][x][3]==false && wallMap[y - 1][x][1]==false) return true;
		}
		else if (d == 2) {
			if (wallMap[y][x][1]==false && wallMap[y][x - 1][2]==false) return true;
		}
		else if (d == 3) {
			if (wallMap[y][x][1]==false && wallMap[y][x - 1][3]==false) return true;
		}
	}
	else if (i == 2) {
		if (d == 0) {
			if (wallMap[y][x][2]==false && wallMap[y + 1][x][0]==false) return true;
		}
		else if (d == 1) {
			if (wallMap[y][x][2]==false && wallMap[y + 1][x][1]==false) return true;
		}
		else if (d == 2) {
			if (wallMap[y][x][0]==false && wallMap[y][x + 1][2]==false) return true;
		}
		else if (d == 3) {
			if (wallMap[y][x][0]==false && wallMap[y][x + 1][3]==false) return true;
		}
	}
	return false;	
}

`🌡️3. Control Temperature`

바람의 양을 조절하는 부분은 모든 칸에 대해서 동시에 발생하기 때문에 온도 변화의 가중치를 저장하는 int tmp[][]을 하나 만들어준다
모든 칸에 대해서 인접한 칸과 비교를 해서 온도를 조절한다는 뜻은 한 칸에 대해서 상,하,좌,우 4개의 칸과 비교를 해본다는 뜻이다

다음과 같이 한 칸을 탐색할 때 네 칸을 모두 비교해보아야 하지만 앞에서 이미 비교했던 칸은 제외를 해야한다-> 동쪽과 남쪽만 비교해보면 된다

void control_temperature() {
	int tmp[MAX][MAX] = { 0, };

	for (int y = 1; y <= R; y++) {
		for (int x = 1; x <= C; x++) {
			for (int i = 0; i < 2; i++) {
				int dir = i==0 ? 0 : 2;

				int ny = y + dy[dir];
				int nx = x + dx[dir];

				if (ny <= 0 || nx <= 0 || ny > R || nx > C) continue;
				if (wallMap[y][x][dir]==false) {
					pair<int, int> maxCoord, minCoord;
					if (map[y][x] > map[ny][nx]) {
						maxCoord = { y,x };
						minCoord = { ny, nx };
					}
					else {
						maxCoord = { ny, nx };
						minCoord = { y,x };
					}

					int diff = abs(map[y][x] - map[ny][nx]);
					diff /= 4;
					tmp[maxCoord.first][maxCoord.second] -= diff;
					tmp[minCoord.first][minCoord.second] += diff;
				}
			}
		}
	}
	
	for (int i = 1; i <= R; i++)
		for (int j = 1; j <= C; j++)
			map[i][j] += tmp[i][j];
}

`🌡️4. Decrease Temperatrue`

가장 바깥쪽 칸의 온도를 1도씩 감소시킨다
이때 겹칠 수 있는 부분에 주의한다

void decrease_temperatrue() {
	for (int i = 1; i <= C; i++) {
		if (map[1][i] > 0) map[1][i]--;
		if (map[R][i] > 0) map[R][i]--;
	}
	
	for (int i = 2; i < R; i++) {
		if (map[i][1] > 0) map[i][1]--;
		if (map[i][C] > 0) map[i][C]--;
	}
}

`🌡️Source Code`

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

const int dy[] = { 0,0,1,-1 };
const int dx[] = { 1,-1,0,0 };

const int wdy[4][3] = { {-1,0,1}, {-1,0,1}, {1,1,1}, {-1, - 1, - 1}};
const int wdx[4][3] = { {1,1,1}, {-1,-1,-1}, {-1,0,1}, {-1,0,1} };

const int MAX = 21;

using namespace std;

int R, C, K, W;

vector <pair<int, int>> pos;
vector <pair<pair<int, int>, int>> wall, heater;

vector<vector<int>> map;
bool wallMap[MAX][MAX][4];

void print() {
	printf("\n");
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			printf("%2d ", map[i][j]);
		}
		printf("\n");
	}
}

void input() {
	cin >> R >> C >> K;

	map = vector<vector<int>>(R + 1, vector<int>(C + 1));

	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			cin >> map[i][j];
			if (map[i][j] != 0 && map[i][j] != 5)
				heater.push_back(make_pair(make_pair(i, j), map[i][j]));
			else if (map[i][j] == 5)
				pos.push_back(make_pair(i, j));
			map[i][j] = 0;
		}
	}
	cin >> W;
	for (int i = 0; i < W; i++) {
		int a, b, c; cin >> a >> b >> c;
		wall.push_back(make_pair(make_pair(a, b), c));
	}
	
}

void setting_wall() {
	for (int i = 0; i < W; i++) {
		int y = wall[i].first.first;
		int x = wall[i].first.second;
		int t = wall[i].second;

		/*
		t==0 : (y,x)기준으로 북(3)쪽에 벽
		t==1 : (y,x)기준으로 동(0)쪽에 벽
		*/
		if (t == 0) {
			wallMap[y][x][3] = true;
			wallMap[y - 1][x][2] = true;
		}
		else if (t == 1) {
			wallMap[y][x][0] = true;
			wallMap[y][x + 1][1] = true;
		}
	}
}

bool check_wall(int y, int x, int d, int i) {

	// (y,x)에서 현재 방향 d로 벽이 없다면 이동 가능
	if (i == 1) {
		if (wallMap[y][x][d]==false) return true;
	}

	// 0=동, 1=서, 2=남, 3=북
	else if (i == 0) {
		if (d == 0) {
			if (wallMap[y][x][3]==false && wallMap[y - 1][x][0]==false) return true;
		}
		else if (d == 1) {
			if (wallMap[y][x][3]==false && wallMap[y - 1][x][1]==false) return true;
		}
		else if (d == 2) {
			if (wallMap[y][x][1]==false && wallMap[y][x - 1][2]==false) return true;
		}
		else if (d == 3) {
			if (wallMap[y][x][1]==false && wallMap[y][x - 1][3]==false) return true;
		}
	}
	else if (i == 2) {
		if (d == 0) {
			if (wallMap[y][x][2]==false && wallMap[y + 1][x][0]==false) return true;
		}
		else if (d == 1) {
			if (wallMap[y][x][2]==false && wallMap[y + 1][x][1]==false) return true;
		}
		else if (d == 2) {
			if (wallMap[y][x][0]==false && wallMap[y][x + 1][2]==false) return true;
		}
		else if (d == 3) {
			if (wallMap[y][x][0]==false && wallMap[y][x + 1][3]==false) return true;
		}
	}
	return false;	
}

int change_dir(int d) {
	switch (d) {
	case 1: return 0;
	case 2: return 1;
	case 3: return 3;
	case 4: return 2;
	}
}

void spread(int y, int x, int d) {
	bool update[MAX][MAX] = { false, };

	d = change_dir(d);
	y += dy[d];
	x += dx[d];

	if (y <= 0 || x <= 0 || y > R || x > C) return;

	// (y,x)좌표, 온도
	queue <pair<pair<int, int>, int>> q;
	q.push(make_pair(make_pair(y, x), 5));

	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int wind = q.front().second;

		q.pop();

		map[y][x] += wind;
		if (wind == 1) continue;

		for (int i = 0; i < 3; i++) {
			int ny = y + wdy[d][i];
			int nx = x + wdx[d][i];

			if (ny <= 0 || nx <= 0 || ny > R || nx > C) continue;

			if (update[ny][nx]==false && check_wall(y, x, d, i) == true) {
				update[ny][nx] = true;
				q.push(make_pair(make_pair(ny, nx), wind - 1));
			}
		}
	}
}

void spread_wind() {
	for (int i = 0; i < heater.size(); i++) {
		int y = heater[i].first.first;
		int x = heater[i].first.second;
		int d = heater[i].second;

		spread(y, x, d);
	}
}

void control_temperature() {
	int tmp[MAX][MAX] = { 0, };

	for (int y = 1; y <= R; y++) {
		for (int x = 1; x <= C; x++) {
			for (int i = 0; i < 2; i++) {
				int dir = i==0 ? 0 : 2;

				int ny = y + dy[dir];
				int nx = x + dx[dir];

				if (ny <= 0 || nx <= 0 || ny > R || nx > C) continue;
				if (wallMap[y][x][dir]==false) {
					pair<int, int> maxCoord, minCoord;
					if (map[y][x] > map[ny][nx]) {
						maxCoord = { y,x };
						minCoord = { ny, nx };
					}
					else {
						maxCoord = { ny, nx };
						minCoord = { y,x };
					}

					int diff = abs(map[y][x] - map[ny][nx]);
					diff /= 4;
					tmp[maxCoord.first][maxCoord.second] -= diff;
					tmp[minCoord.first][minCoord.second] += diff;
				}
			}
		}
	}
	
	for (int i = 1; i <= R; i++)
		for (int j = 1; j <= C; j++)
			map[i][j] += tmp[i][j];
}

void decrease_temperatrue() {
	for (int i = 1; i <= C; i++) {
		if (map[1][i] > 0) map[1][i]--;
		if (map[R][i] > 0) map[R][i]--;
	}
	
	for (int i = 2; i < R; i++) {
		if (map[i][1] > 0) map[i][1]--;
		if (map[i][C] > 0) map[i][C]--;
	}
}

bool check() {
	for (int i = 0; i < pos.size(); i++) {
		int y = pos[i].first;
		int x = pos[i].second;

		if (map[y][x] < K) return false;
	}
	return true;
}

void solution() {
	setting_wall();

	int chocolate = 0;

	while (1) {
		if (chocolate > 100) break;

		spread_wind();

		//print();

		control_temperature();

		//print();

		decrease_temperatrue();

		chocolate++;

		//print();

		if (check()) break;
	}
	cout << chocolate << endl;
}

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

	input();
	solution();

	return 0;
}

Author And Source

이 문제에 관하여(<Baekjoon> #23289 Simulation_온풍기 안녕! c++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmy/Baekjoon-23289-Simulation온풍기-안녕-c

우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)

[02] TypeScript 기본 타입

엘리스 SW 엔지니어링 🐰 - DOM과 Node 객체

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다