백준 23289 온풍기 안녕!
https://www.acmicpc.net/problem/23289
23289번: 온풍기 안녕!
유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기
www.acmicpc.net
- 빡구현 문제이다. 시간 복잡도는 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;
}