백준 23289 온풍기 안녕!

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

23289번: 온풍기 안녕!

 

- 빡구현 문제이다. 시간 복잡도는 R * C 크기의 map * 만약 모든 칸에 온풍기가 존재한다면, 온도를 확산시키는 과정이 총 R*C 일어나므로, O((RC)^2)이다. 하지만 시간복잡도 조절을 위해 이 과정이 최대 101번정도 이루어지므로, 시간초과 걱정은 X

 

- 가장 먼저, map의 정보를 입력받는다. 여기서 문제에 주어진 조건대로, map의 값이 1~4이면 온풍기, 5이면 체크해야 하는 칸임을 표시해야 한다. 필자는 heater 벡터를 활용하여 좌표와 방향을 담았는데, 이 때 문제에서 주어진 순서대로, 즉 1은 동, 2는 서, 3은 북, 4는 남 이런식으로 담지 않고 0,1,2,3을 각각 동,남,서,북으로 담았다. 이유는 나중에 온풍기의 온도 확산과정에서 코드를 더 간단하게 작성할 수 있기 때문이다.(이 부분에서 1차 시행착오)

 

- 다음으로, 벽의 정보를 입력받는다.  필자는 3차원 배열 wall[x][y][z]를 활용했다. 이것은 (x,y)에 있는 장애물의 정보(z)를 의미한다. 만약 0인 경우는 해당 좌표의 오른쪽, 1인 경우는 해당 좌표의 위쪽에 장애물이 있는 것이다.

 

- 이제 문제에서 주어진 작업을 while문 내에서 실행한다.

 

 

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

 

 

 

- heater 벡터에 담아두었던 온풍기의 좌표 및 방향 정보를 꺼내서 확산(bfs)를 실행한다. 이 때, 총 3가지의 경우의 수를 조사해야 한다.

 

  1) 온풍기의 방향의 왼쪽 대각선

  2) 온풍기의 방향의 정면

  3) 온풍기의 방향의 오른쪽 대각선

 

- 여기서, while문 내에서 모두 해결을 하는데, 큐에서 하나씩 빼서 이 3가지의 경우의 수를 조사하고, 만약 조건을 만족하는 경우 큐에 넣는 식으로 진행을 한다. (BFS의 응용) 왼쪽 대각선의 경우, 먼저 온풍기 방향의 왼쪽으로 이동 가능한지를 체크 한 후, 그 위치에서 다시 온풍기 방향으로 추가 이동이 가능한 지를 체크한다. 이 후, 이동이 가능하다면 해당 좌표와 현재 온도(score) - 1 값을 큐에 넣는다.

 

- 정면의 경우는 온풍이 방향으로 이동이 가능한지만을 체크하면 된다.

 

- 오른쪽 대각선의 경우도 왼쪽 대각선과 동일한 로직으로 작동한다.

 

- 여기서, 중복되는 로직이 많아지므로, 현재 좌표와 방향이 주어질 때 해당 방향으로의 이동이 가능한지를 체크하는 can_move 함수를 정의해서 활용한다. 모든 온도 확산 결과는 temp_map에 한 번에 담아주고, 모든 heater가 확산을 마쳤다면 temp_map을 temparature에 더해주는 sum_map 함수를 실행한다.

 

2. 온도가 조절됨

 

 

 

- 주어진 좌표의 인접한 좌표들을 확인하면서, 만약 현재 좌표보다 값이 작은 경우에만 확산을 해 준다. 물론 조심해야 할 것은 temparature 배열을 그대로 사용하지 말고, temp_map에 확산 결과를 저장해서 나중에 한 번에 temparature 에 업데이트를 해 주어야 한다. 이 부분은 삼성의 단골 레퍼토리라 잘 익혀야 한다.

 

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

 

 

- 간단하게 for문 활용하여 해결한다.

 

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

 

 

- answer 변수에 ++ 해 준다. 이 때, 문제에서 101을 넘어가지 말라 했으므로, 101이 된다면 가차없이 break를 해서 while문을 탈출한다.

 

 

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

 

 

- inspection 벡터에 담아두었던 좌표를 꺼내서, 하나씩 비교한다. 만약 한 칸이라도 K보다 작다면, 테스트를 이어간다.

 

 

 

 

 

 

- 대략 2시간 반 정도가 걸렸다. 구현 난이도 자체는 매우 어렵거나 하진 않았지만 고려해야 할 것들이 많이 있어서, 시간이 굉장히 많이 걸리는 문제인 것 같다.

 

 

- 디버깅 한 것들

 

 

1. 큐에 다음 좌표를 넣을 때, 총 3가지의 경우의 수를 파악해야 하는데, 각 경우의 수에서 만약 해당 경우의 수가 큐에 들어가지 않으면 바로 continue를 해버리는 바람에, 남은 경우의 수를 파악하지 못한 문제점이 발생했다.

 

2. 온도 조절 단계에서 , (현재 온도 - 조사중인 온도 ) / 4를 구해야 했는데, (현재 온도) / 4를 구하여 문제가 발생했다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
bool wall[21][21][2];
int temparature[21][21];
vector<pair<int, int>> inspection;
vector<pair<pair<int, int>, int >> heater;
int r, c, k,w;
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
bool visited[21][21];
int temp_map[21][21];
void debugging() {
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			cout << temparature[i][j] << " ";
		}
		cout << '\n';
	}
	cout << '\n';
}
bool can_move(int x, int y, int dir) {
	if (dir == 0) {
		if (wall[x][y][1]) return false;
		x += dx[dir]; y += dy[dir];
		if (x < 1 || x > r || y < 1 || y > c) return false;
	}
	else if (dir == 1) {
		x += dx[dir]; y += dy[dir];
		if (x < 1 || x > r || y < 1 || y > c) return false;
		if (wall[x][y][0]) return false;
	}
	else if (dir == 2) {
		x += dx[dir]; y += dy[dir];
		if (x < 1 || x > r || y < 1 || y > c) return false;
		if (wall[x][y][1]) return false;
	}
	else if (dir == 3) {
		if (wall[x][y][0]) return false;
		x += dx[dir]; y += dy[dir];
		if (x < 1 || x > r || y < 1 || y > c) return false;
	}
	return true;
}
void minus_edge() {
	//차례대로 위, 오른쪽, 아래, 왼쪽 제거
	for (int i = 1; i <= c; i++) {
		if(temparature[1][i] > 0) temparature[1][i]--;
	}
	for (int i = 2; i <= r; i++) {
		if (temparature[i][c] > 0) temparature[i][c]--;
	}
	for (int i = c-1; i >= 1; i--) {
		if (temparature[r][i] > 0) temparature[r][i]--;
	}
	for (int i = r-1; i >= 2; i--) {
		if (temparature[i][1] > 0) temparature[i][1]--;
	}
}
void control(int x, int y) {
	int now_score = temparature[x][y];
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i]; int ny = y + dy[i];
		if (!can_move(x, y, i)) continue;
		if (now_score <= temparature[nx][ny]) continue;
		temp_map[nx][ny] += ((now_score - temparature[nx][ny]) / 4);
		temp_map[x][y] -= ((now_score - temparature[nx][ny]) / 4);
	}
}

void sum_map() {
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			temparature[i][j] += temp_map[i][j];
		}
	}
	memset(temp_map, 0, sizeof(temp_map));
}
void bfs(int x, int y,int dir) {
	queue<pair<pair<int, int>,int>> q;
	int nx = x + dx[dir]; int ny = y + dy[dir];
	if (nx < 1 || nx > r || ny < 1 || ny > c) return;
	visited[nx][ny] = true;
	q.push({ {nx,ny}, 5});
	while (!q.empty()) {
		int tx = q.front().first.first;
		int ty = q.front().first.second;
		int score = q.front().second;
		temp_map[tx][ty] += score;
		q.pop();
		if (score == 0) continue;
		int left_dir = (dir + 3) % 4; int right_dir = (dir + 1) % 4;
		//3가지 방향 조사. 1.현재 방향의 왼쪽 대각선
		int nx = tx; int ny = ty;
		if (can_move(nx, ny, left_dir)) {
			nx += dx[left_dir]; ny += dy[left_dir];
			if (can_move(nx, ny, dir)) {
				nx += dx[dir]; ny += dy[dir];
				if (!visited[nx][ny]) {
					q.push({ { nx,ny }, score - 1 });
					visited[nx][ny] = true;
				}
			}
		}
		//3가지 방향 조사. 2. 정면
		nx = tx; ny = ty;
		if (can_move(nx, ny, dir)) {
			nx += dx[dir]; ny += dy[dir];
			if (!visited[nx][ny]) {
				q.push({ { nx,ny }, score - 1 });
				visited[nx][ny] = true;
			}
		}
		//3가지 방향 조사 3. 오른쪽 대각선
		nx = tx; ny = ty;
		if (can_move(nx, ny, right_dir)) {
			nx += dx[right_dir]; ny += dy[right_dir];
			if (can_move(nx, ny, dir)) {
				nx += dx[dir]; ny += dy[dir];
				if (!visited[nx][ny]) {
					q.push({ { nx,ny }, score - 1 });
					visited[nx][ny] = true;
				}
			}
		}
	}
	
}
int main() {
	int answer = 0;
	cin >> r >> c >> k;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			int temp; cin >> temp;
			temparature[i][j] = temp;
			if (temp > 0) {
				if(temp==1) heater.push_back({ {i,j}, 0 });
				else if(temp==2) heater.push_back({ {i,j}, 2 });
				else if(temp==3) heater.push_back({ {i,j}, 3 });
				else if(temp==4) heater.push_back({ {i,j}, 1 });
				else inspection.push_back({ i,j });
				temparature[i][j] = 0;
			}
		}
	}
	cin >> w;
	for (int i = 0; i < w; i++) {
		int x, y, t;
		cin >> x >> y >> t;
		wall[x][y][t] = 1;
	}
	while (1) { // 시작
		for (int i = 0; i < heater.size(); i++) {
			int x = heater[i].first.first; int y = heater[i].first.second;
			int dir = heater[i].second;
			bfs(x, y, dir);
			sum_map();
			memset(visited, false, sizeof(visited));
		}
		for (int i = 1; i <= r; i++) {
			for (int j = 1; j <= c; j++) {
				if (!temparature[i][j]) continue;
				control(i, j);
			}
		}
		sum_map();
		minus_edge();
		answer++;
		if (answer == 101) break;
		bool flag = false;
		for (int i = 0; i < inspection.size(); i++) {
			int x = inspection[i].first; int y = inspection[i].second;
			if (temparature[x][y] < k) flag = true;
		}
		if (!flag) break;
	}
	cout << answer;
	return 0;
}