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

well-life-gm·2021년 10월 28일
백준백준 삼성알고리즘
0

백준 삼성

목록 보기
1/23

온풍기 안녕!

아 이거 왜 못풀었지; 집에서 푸니까 금방푼다; 심지어 원트에 성공함;
문제에서 주어진대로 하면 된다.

일단 아래 코드는 메인 부분 코드이다.
time을 늘리면서 100이 열 확산, 열 교환, 냉각 과정을 한 뒤 Check를 하면 된다.
만약 100이 넘어가면 break를 해준다.

int main(void)
{
	int r, c, k, w;
	
	cin >> r >> c >> k;
	vector<vector<int>> map(r, vector<int>(c, 0));
	
	vector<heater_pos> heaters;
	for (int i = 0; i < r; i++) 
		for (int j = 0; j < c; j++) {
			cin >> map[i][j];
			if (map[i][j] != 5 && map[i][j] != 0) 
				heaters.push_back({ i, j, map[i][j] });
		}
	rowSize = r;
	colSize = c;
	
	cin >> w;
	// 0이면 위쪽 벽, 1이면 오른쪽 벽
	vector<vector<int>> walls(w, vector<int>(3, 0));
	for (int i = 0; i < w; i++) {
		cin >> walls[i][0] >> walls[i][1] >> walls[i][2];
		if (walls[i][2] == 0) 
			top_wall[walls[i][0] - 1][walls[i][1] - 1] = 1;
		else 
			right_wall[walls[i][0] - 1][walls[i][1] - 1] = 1;
	}

	int time = 1;
	while (1) {
		Spread(map, heaters, walls);
		Control(walls);
		Cold();
		if (Check(map, k))
			break;
		time++;
		if (time > 100)
			break;
	}
	if (time > 100)
		time = 101;

	cout << time << "\n";
	
	return 0;
}

확산 조건

확산 조건은 위 그림과 같다. 

void Spread(vector<vector<int>> &map, 
	vector<heater_pos> heaters, const vector<vector<int>> walls)
{
	for (const heater_pos h : heaters) {
		int visit_map[21][21] = { 0 , };

		int heat_cnt = HEAT;
		queue<pos> q;

		pos base = { h.row + rowDir[h.dir], h.col + colDir[h.dir], heat_cnt };
		q.push(base);
		visit_map[base.row][base.col] = 1;

		while (1) {
			if (q.empty())
				break;
			pos heat = q.front(); q.pop();
			heat_map[heat.row][heat.col] += heat.heat;
			
			if (heat.heat == 1)
				continue;
			
			int new_row, new_col, new_heat;
			
			if (h.dir == 1) { // 오른쪽
				new_col = heat.col + 1;
				if (new_col >= colSize)
					continue;
				new_heat = heat.heat - 1;
				for (int i = 0; i < 3; i++) {
					new_row = heat.row + i - 1;
					if (new_row < 0 || new_row >= rowSize)
						continue;
					if (i == 0) {
						if (heat.row - 1 < 0)
							continue;
						if (top_wall[heat.row][heat.col] == 1 ||
							right_wall[heat.row - 1][heat.col] == 1)
							continue;
					}
					else if (i == 1) {
						if (right_wall[heat.row][heat.col] == 1)
							continue;
					}
					else if (i == 2) {
						if (heat.row + 1 >= rowSize)
							continue;
						if (top_wall[heat.row + 1][heat.col] == 1 ||
							right_wall[heat.row + 1][heat.col] == 1)
							continue;
					}
					if (visit_map[new_row][new_col] == 1)
						continue;

					q.push({ new_row, new_col, new_heat });
					visit_map[new_row][new_col] = 1;
				}
			}
			else if (h.dir == 2) { // 왼쪽
				new_col = heat.col - 1;
				if (new_col < 0)
					continue;
				new_heat = heat.heat - 1;
				for (int i = 0; i < 3; i++) {
					new_row = heat.row + i - 1;
					if (new_row < 0 || new_row >= rowSize)
						continue;
					if (i == 0) {
						if (heat.row - 1 < 0)
							continue;
						if (heat.col - 1 < 0)
							continue;
						if (top_wall[heat.row][heat.col] == 1 ||
							right_wall[heat.row - 1][heat.col - 1] == 1)
							continue;
					}
					else if (i == 1) {
						if (heat.col - 1 < 0)
							continue;
						if (right_wall[heat.row][heat.col - 1] == 1)
							continue;
					}
					else if (i == 2) {
						if (heat.row + 1 >= rowSize)
							continue;
						if (heat.col - 1 < 0)
							continue;
						if (top_wall[heat.row + 1][heat.col] == 1 ||
							right_wall[heat.row + 1][heat.col - 1] == 1)
							continue;
					}
					if (visit_map[new_row][new_col] == 1)
						continue;

					q.push({ new_row, new_col, new_heat });
					visit_map[new_row][new_col] = 1;
				}
			}
			else if (h.dir == 3) { // 위쪽
				new_row = heat.row - 1;
				if (new_row < 0)
					continue;
				new_heat = heat.heat - 1;
				for (int i = 0; i < 3; i++) {
					new_col = heat.col + i - 1;
					if (new_col < 0 || new_col >= colSize)
						continue;
					if (i == 0) {
						if (heat.col - 1 < 0)
							continue;
						if (top_wall[heat.row][heat.col - 1] == 1 ||
							right_wall[heat.row][heat.col - 1] == 1)
							continue;
					}
					else if (i == 1) {
						if (top_wall[heat.row][heat.col] == 1)
							continue;
					}
					else if (i == 2) {
						if (heat.col + 1 >= colSize)
							continue;
						if (top_wall[heat.row][heat.col + 1] == 1 ||
							right_wall[heat.row][heat.col] == 1)
							continue;
					}
					if (visit_map[new_row][new_col] == 1)
						continue;

					q.push({ new_row, new_col, new_heat });
					visit_map[new_row][new_col] = 1;
				}
			}
			else if (h.dir == 4) { // 아래쪽
				new_row = heat.row + 1;
				if (new_row >= rowSize)
					continue;
				new_heat = heat.heat - 1;
				for (int i = 0; i < 3; i++) {
					new_col = heat.col + i - 1;
					if (new_col < 0 || new_col >= colSize)
						continue;
					if (i == 0) {
						if (heat.row + 1 >= rowSize)
							continue;
						if (heat.col - 1 < 0)
							continue;
						if (top_wall[heat.row + 1][heat.col - 1] == 1 ||
							right_wall[heat.row][heat.col - 1] == 1)
							continue;
					}
					else if (i == 1) {
						if (heat.row + 1 >= rowSize)
							continue;
						if (top_wall[heat.row + 1][heat.col] == 1)
							continue;
					}
					else if (i == 2) {
						if (heat.row + 1 >= rowSize)
							continue;
						if (heat.col + 1 >= colSize)
							continue;
						if (top_wall[heat.row + 1][heat.col + 1] == 1 ||
							right_wall[heat.row][heat.col] == 1)
							continue;
					}
					if (visit_map[new_row][new_col] == 1)
						continue;

					q.push({ new_row, new_col, new_heat });
					visit_map[new_row][new_col] = 1;
				}
			}	
			
		}
	}
}

코드가 좀 긴데, 확산을 위해서 Queue를 활용했고, 위 그림의 벽 조건을 체크하면서 확산이 가능한 영역인지 아닌지를 체크해주면 된다. 그리고 확산 중 이미 방문한 지역을 중복으로 방문할 수도 있기 때문에 visit_map을 관리한다.

void Control(const vector<vector<int>> walls)
{
	int new_row, new_col;
	int heat_change[21][21] = { 0, };

	// 1,2,3,4 : 오른 왼 위 아래
	for (int i = 0; i < rowSize; i++) {
		for (int j = 0; j < colSize; j++) {
			int decrease = 0;
			for (int k = 1; k < 5; k++) {
				new_row = i + rowDir[k];
				new_col = j + colDir[k];
				if (new_row < 0 || new_row >= rowSize)
					continue;
				if (new_col < 0 || new_col >= colSize)
					continue;
				if (k == 1) {
					if (right_wall[i][j] == 1)
						continue;
				} 
				else if(k == 2) {
					if (right_wall[new_row][new_col] == 1)
						continue;
				}
				else if (k == 3) {
					if (top_wall[i][j] == 1)
						continue;
				}
				else if (k == 4) {
					if (top_wall[new_row][new_col] == 1)
						continue;
				}

				if (heat_map[i][j] <= heat_map[new_row][new_col])
					continue;

				int amount = (int)(heat_map[i][j] - heat_map[new_row][new_col]) / 4;
				heat_change[new_row][new_col] += amount;
				heat_change[i][j] -= amount;
			}
		}
	}

	for (int i = 0; i < rowSize; i++) 
		for (int j = 0; j < colSize; j++) 
			heat_map[i][j] += heat_change[i][j];
}

열 교환을 하는 부분이다. 함수명은 Change가 더 좋았을지도?

모든 곳에서 동시에 발생한다 했으니까 inplace로 update는 못하고, outplace로 update하기 위해서 heat_change를 따로 관리한다.

벽 조건에 맞춰서 열을 교환해주면 된다.
중복적으로 업데이트하는 것을 방지하기 위해서 i, j의 열이 나머지 4방향보다 클 때만 열교환을 해준다.

void Cold()
{
	for (int i = 0; i < rowSize; i++) 
		for (int j = 0; j < colSize; j++) 
			if (i == 0 || i == rowSize - 1 || j == 0 || j == colSize - 1) 
				if (heat_map[i][j] > 0)
					heat_map[i][j] -= 1;
}

bool Check(const vector<vector<int>> map, int k)
{
	bool isFin = true;
	for (int i = 0; i < rowSize; i++) {
		for (int j = 0; j < colSize; j++) {
			if (map[i][j] == 5 && heat_map[i][j] < k) {
				isFin = false;
				goto out;
			}
		}
	}

out:
	return isFin;
}

외곽 지역을 1씩 줄이는 것과 Check하는 것은 금방한다.
더 효율적으로 할 수 있었을 것 같은데 간단하게 그냥 2중 loop으로 했다...

전체 코드 
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;


int rowSize;
int colSize;

typedef struct __heater_pos {
	int row;
	int col;
	int dir;
} heater_pos;

typedef struct __pos {
	int row;
	int col;
	int heat;
} pos;

// 1,2,3,4 : 오른 왼 위 아래
int rowDir[5] = { 0, 0, 0, -1, 1 };
int colDir[5] = { 0, 1, -1, 0, 0 };

#define HEAT 5

int top_wall[21][21];
int right_wall[21][21];
int heat_map[21][21];

void Print_Map(string s)
{
	printf("Print Map [%s] \n", s.c_str());
	for (int i = 0; i < rowSize; i++) {
		for (int j = 0; j < colSize; j++) 
			printf("%d ", heat_map[i][j]);
		printf("\n");
	}
}

void Spread(vector<vector<int>> &map, 
	vector<heater_pos> heaters, const vector<vector<int>> walls)
{
	for (const heater_pos h : heaters) {
		int visit_map[21][21] = { 0 , };

		int heat_cnt = HEAT;
		queue<pos> q;

		pos base = { h.row + rowDir[h.dir], h.col + colDir[h.dir], heat_cnt };
		q.push(base);
		visit_map[base.row][base.col] = 1;

		while (1) {
			if (q.empty())
				break;
			pos heat = q.front(); q.pop();
			heat_map[heat.row][heat.col] += heat.heat;
			
			if (heat.heat == 1)
				continue;
			
			int new_row, new_col, new_heat;
			
			if (h.dir == 1) { // 오른쪽
				new_col = heat.col + 1;
				if (new_col >= colSize)
					continue;
				new_heat = heat.heat - 1;
				for (int i = 0; i < 3; i++) {
					new_row = heat.row + i - 1;
					if (new_row < 0 || new_row >= rowSize)
						continue;
					if (i == 0) {
						if (heat.row - 1 < 0)
							continue;
						if (top_wall[heat.row][heat.col] == 1 ||
							right_wall[heat.row - 1][heat.col] == 1)
							continue;
					}
					else if (i == 1) {
						if (right_wall[heat.row][heat.col] == 1)
							continue;
					}
					else if (i == 2) {
						if (heat.row + 1 >= rowSize)
							continue;
						if (top_wall[heat.row + 1][heat.col] == 1 ||
							right_wall[heat.row + 1][heat.col] == 1)
							continue;
					}
					if (visit_map[new_row][new_col] == 1)
						continue;

					q.push({ new_row, new_col, new_heat });
					visit_map[new_row][new_col] = 1;
				}
			}
			else if (h.dir == 2) { // 왼쪽
				new_col = heat.col - 1;
				if (new_col < 0)
					continue;
				new_heat = heat.heat - 1;
				for (int i = 0; i < 3; i++) {
					new_row = heat.row + i - 1;
					if (new_row < 0 || new_row >= rowSize)
						continue;
					if (i == 0) {
						if (heat.row - 1 < 0)
							continue;
						if (heat.col - 1 < 0)
							continue;
						if (top_wall[heat.row][heat.col] == 1 ||
							right_wall[heat.row - 1][heat.col - 1] == 1)
							continue;
					}
					else if (i == 1) {
						if (heat.col - 1 < 0)
							continue;
						if (right_wall[heat.row][heat.col - 1] == 1)
							continue;
					}
					else if (i == 2) {
						if (heat.row + 1 >= rowSize)
							continue;
						if (heat.col - 1 < 0)
							continue;
						if (top_wall[heat.row + 1][heat.col] == 1 ||
							right_wall[heat.row + 1][heat.col - 1] == 1)
							continue;
					}
					if (visit_map[new_row][new_col] == 1)
						continue;

					q.push({ new_row, new_col, new_heat });
					visit_map[new_row][new_col] = 1;
				}
			}
			else if (h.dir == 3) { // 위쪽
				new_row = heat.row - 1;
				if (new_row < 0)
					continue;
				new_heat = heat.heat - 1;
				for (int i = 0; i < 3; i++) {
					new_col = heat.col + i - 1;
					if (new_col < 0 || new_col >= colSize)
						continue;
					if (i == 0) {
						if (heat.col - 1 < 0)
							continue;
						if (top_wall[heat.row][heat.col - 1] == 1 ||
							right_wall[heat.row][heat.col - 1] == 1)
							continue;
					}
					else if (i == 1) {
						if (top_wall[heat.row][heat.col] == 1)
							continue;
					}
					else if (i == 2) {
						if (heat.col + 1 >= colSize)
							continue;
						if (top_wall[heat.row][heat.col + 1] == 1 ||
							right_wall[heat.row][heat.col] == 1)
							continue;
					}
					if (visit_map[new_row][new_col] == 1)
						continue;

					q.push({ new_row, new_col, new_heat });
					visit_map[new_row][new_col] = 1;
				}
			}
			else if (h.dir == 4) { // 아래쪽
				new_row = heat.row + 1;
				if (new_row >= rowSize)
					continue;
				new_heat = heat.heat - 1;
				for (int i = 0; i < 3; i++) {
					new_col = heat.col + i - 1;
					if (new_col < 0 || new_col >= colSize)
						continue;
					if (i == 0) {
						if (heat.row + 1 >= rowSize)
							continue;
						if (heat.col - 1 < 0)
							continue;
						if (top_wall[heat.row + 1][heat.col - 1] == 1 ||
							right_wall[heat.row][heat.col - 1] == 1)
							continue;
					}
					else if (i == 1) {
						if (heat.row + 1 >= rowSize)
							continue;
						if (top_wall[heat.row + 1][heat.col] == 1)
							continue;
					}
					else if (i == 2) {
						if (heat.row + 1 >= rowSize)
							continue;
						if (heat.col + 1 >= colSize)
							continue;
						if (top_wall[heat.row + 1][heat.col + 1] == 1 ||
							right_wall[heat.row][heat.col] == 1)
							continue;
					}
					if (visit_map[new_row][new_col] == 1)
						continue;

					q.push({ new_row, new_col, new_heat });
					visit_map[new_row][new_col] = 1;
				}
			}	
			
		}
	}
}

void Control(const vector<vector<int>> walls)
{
	int new_row, new_col;
	int heat_change[21][21] = { 0, };

	// 1,2,3,4 : 오른 왼 위 아래
	for (int i = 0; i < rowSize; i++) {
		for (int j = 0; j < colSize; j++) {
			int decrease = 0;
			for (int k = 1; k < 5; k++) {
				new_row = i + rowDir[k];
				new_col = j + colDir[k];
				if (new_row < 0 || new_row >= rowSize)
					continue;
				if (new_col < 0 || new_col >= colSize)
					continue;
				if (k == 1) {
					if (right_wall[i][j] == 1)
						continue;
				} 
				else if(k == 2) {
					if (right_wall[new_row][new_col] == 1)
						continue;
				}
				else if (k == 3) {
					if (top_wall[i][j] == 1)
						continue;
				}
				else if (k == 4) {
					if (top_wall[new_row][new_col] == 1)
						continue;
				}

				if (heat_map[i][j] <= heat_map[new_row][new_col])
					continue;

				int amount = (int)(heat_map[i][j] - heat_map[new_row][new_col]) / 4;
				heat_change[new_row][new_col] += amount;
				heat_change[i][j] -= amount;
			}
		}
	}

	for (int i = 0; i < rowSize; i++) 
		for (int j = 0; j < colSize; j++) 
			heat_map[i][j] += heat_change[i][j];
}

void Cold()
{
	for (int i = 0; i < rowSize; i++) 
		for (int j = 0; j < colSize; j++) 
			if (i == 0 || i == rowSize - 1 || j == 0 || j == colSize - 1) 
				if (heat_map[i][j] > 0)
					heat_map[i][j] -= 1;
}

bool Check(const vector<vector<int>> map, int k)
{
	bool isFin = true;
	for (int i = 0; i < rowSize; i++) {
		for (int j = 0; j < colSize; j++) {
			if (map[i][j] == 5 && heat_map[i][j] < k) {
				isFin = false;
				goto out;
			}
		}
	}

out:
	return isFin;
}
int main(void)
{
	int r, c, k, w;
	
	cin >> r >> c >> k;
	vector<vector<int>> map(r, vector<int>(c, 0));
	
	vector<heater_pos> heaters;
	for (int i = 0; i < r; i++) 
		for (int j = 0; j < c; j++) {
			cin >> map[i][j];
			if (map[i][j] != 5 && map[i][j] != 0) 
				heaters.push_back({ i, j, map[i][j] });
		}
	rowSize = r;
	colSize = c;
	
	cin >> w;
	// 0이면 위쪽 벽, 1이면 오른쪽 벽
	vector<vector<int>> walls(w, vector<int>(3, 0));
	for (int i = 0; i < w; i++) {
		cin >> walls[i][0] >> walls[i][1] >> walls[i][2];
		if (walls[i][2] == 0) 
			top_wall[walls[i][0] - 1][walls[i][1] - 1] = 1;
		else 
			right_wall[walls[i][0] - 1][walls[i][1] - 1] = 1;
	}

	int time = 1;
	while (1) {
		Spread(map, heaters, walls);
		Control(walls);
		Cold();
		if (Check(map, k))
			break;
		time++;
		if (time > 100)
			break;
	}
	if (time > 100)
		time = 101;

	cout << time << "\n";
	
	return 0;
}
profile
well-life-gm
내가 보려고 만든 블로그
다음 포스트

백준 - 이차원 배열과 연산 (17140번)

0개의 댓글

관련 채용 정보