[BOJ] 23289 : 온풍기 안녕!

문제 링크

23289번: 온풍기 안녕! (acmicpc.net)

23289번: 온풍기 안녕!

온풍기를 이용해서 조사하는 칸의 온도가 모두 특정 온도 이상이 되도록 하는데 테스트 과정을 몇 번 거쳐야하는지 계산하는 구현 문제.

여기서는 테스트 과정 한 번을 초콜릿을 하나 먹는 것으로 표현했다.

 

풀이

R x C 크기의 격자에 온풍기가 놓여있다. 이 온풍기에서 바람이 한 번 나오면 문제에서 제시된 그림대로 격자 칸의 온도가 상승하게 된다.

성능 테스트의 과정은 다음과 같다.

1. 집에 있는 모든 온풍기에서 바람이 한 번 나옴
2. 온도가 조절됨
3. 온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소
4. 초콜릿을 하나 먹는다.
5. 조사하는 모든 칸의 온도가 K 이상이 되었는지 검사.
모든 칸의 온도가 K이상이면 테스트를 중단하고, 아니면 1부터 다시 시작한다.

 다음과 같은 성능테스트가 진행됨에 있어 우리가 저장하고 있어야 할 정보들은 어떤 것들이 있을까?

1. 격자판의 현재 온도

각 칸이 현재 몇 도인지 저장하고 있어서 온도 변화와 온도 조사가 가능하다.

int 형의 2차원배열 Map[MAX_N][MAX_N]을 만들어서 각 칸마다의 온도를 저장했다.

온도의 변화가 발생하면 Map의 값을 변경시켜주어야 한다.

 

2. 온풍기의 위치, 방향

온풍기의 좌표와 바라보고있는 방향을 알아야 바람을 보낼 수가 있다.

그런데 온풍기는 몇 개가 설치될지 모르므로 vector를 통해 값을 저장한는 것이 좋다.

vector<pair<pair<int,int>,int>> 를 만들어서 온풍기의 좌표와, 방향 두 가지 정보를 저장했다.

 

 3. 벽의 위치

벽은 인접한 두 칸 사이에 설치될 수 있다. 2차원 배열로 벽의 위치를 표현하기에는 한계가 있다고 생각했다.

만약 ( y, x )와 (y+1, x) 사이에 벽이 있다고 했을 때, 벽위 위치를 2차원 배열로 Wall[y][x] 라고 표시한다면 (y,x) 칸의 상하좌우 방향 중 어떤 위치에 벽이 설치되어있는지 알 수 없다.

그래서 나는 두 칸 사이에 벽이 놓여있음을 표시하기 위해 4차원 배열을 만들었다.

Wall[y][x][y+1][x] 값이 true면 두 좌표 사이에 벽이 놓여있다는 걸로 판단했다.

이때 Wall[y][x][y+1][x] 와 Wall[y+1][x][y][x] 의 값은 항상 같아야한다.

 

4. 조사해야할 칸의 좌표

좌표중 입력값으로 5를 받는 위치만 온도 조사를 해주면 된다.

입력값이 5라면 해당 칸을 inspect라는 pair<int,int> 벡터에 좌표를 저장해서 온도를 조사할 때 사용했다.

 

기본적으로 필요한 정보들은 이 정도가 있다.

나머지는 함수를 어떻게 짜느냐에 따라 알고있어야 할 정보들이 다를 것이다.

 

• 온풍기 바람의 진행

온풍기 바람은 나오는 방향으로 부채꼴 모양으로 퍼져나가며 온풍기에서 멀어질 수록 증가하는 온도가 5->4->3->2->1 순서대로 줄어든다.

바람은 진행하는 방향을 기준으로 진행방향 왼쪽 위 대각선, 위, 오른쪽 위 대각선 방향 이렇게 3방향으로 퍼져나간다.

이때 진행하려는 방향에 벽이 설치되어있다면 해당 방향으로는 바람은 더 이상 진행하지 못한다.

나는 BFS를 이용해서 바람의 진행을 구현했다.

처음 바람이 나오는 칸은 벽으로 막혀있지 않다는 조건이 명시되어 있으므로 큐에 초기값으로 온풍기 바로 앞 칸의 좌표와 증가하는 온도인 5를 넣는다. 이후 앞서 말한 3방향 중 진행이 가능한 방향의 좌표를 큐에 추가적으로 넣어준다. 이때 증가하는 온도 값은 1씩 줄이면서 넣는다. 증가하는 온도가 1인 바람은 더 이상 진행해도 온도변화에 의미가 없으므로 그 바람은 진행을 종료한다.

진행하는 방향 3방향은 특별한 규칙이 없어 노가다로 방향을 정해주었다.

• 온도 조절

모든 칸에 대해서 인접한 4칸에 대해  해당칸과 인접한 칸의 (온도 차이 / 4)를 내림한 만큼 온도가 오고간다. 이때 온도가 높은 칸에서 낮은 칸으로 이동한다. 온도차이가 4이상 나지않으면 해당사항이 없다.

이때 온도 조절은 모든 칸에 대해서 동시에 이루어지기 때문에 값을 바로 조정하지 않고 조정될 값을 temp라는 배열에 미리 담아두고 마지막에 한 번에 온도값을 조절했다.

임의의 두 칸에 대해 온도 조절은 1번만 일어나기 때문에 중복을 방지하기 위해 visited배열을 만들어서 해당 두 칸 사이에 이미 온도 교류가 일어났는지를 기록했다.

• 온도 감소

온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소한다라고 되어있다. 즉 테두리에 대해서 온도가 1이상이면 온도가 1 감소한다는 뜻이다.

반복문으로 테두리만 돌면서 온도가 1 이상이면 온도를 1 낮춰주면 된다.

pair<int, int> direct[4] = { {0,1},{1,0},{0,-1},{-1,0} };
	pair<int, int> now = { 1,1 };
	for (int i = 0; i < 4; i++) {
		if (i % 2 == 0) {
			for (int j = 1; j < C; j++) {
				now = { now.first + direct[i].first, now.second + direct[i].second };
				if (Map[now.first][now.second])
					Map[now.first][now.second]--;
			}
		}
		else {
			for (int j = 1; j < R; j++) {
				now = { now.first + direct[i].first, now.second + direct[i].second };
				if (Map[now.first][now.second])
					Map[now.first][now.second]--;
			}
		}
	}

나는 이런식으로 방향을 오른쪽, 아래, 왼쪽, 위 방향을 설정해두고 now 좌표를 한 칸씩 이동하면서 테두리를 돌았다.

• 온도 조사

온도 조사는 말 그대로 초기에 받아둔 inspect 배열을 이용해서 조사해야할 좌표들의 온도 중 하나라도 K미만인 칸이 있으면 1번 과정으로 돌아가고 아니면 테스트를 중단한다.

테스트 과정을 몇 번 거쳤는지 카운트해서 마지막에 출력해주면 된다. 이때 카운트가 100을 넘어가게되면 테스트를 중단하고 101을 출력하면 된다.

<코드>

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <deque>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 20 + 5;
int Map[MAX_N][MAX_N];
vector<pair<pair<int, int>, int>> Fan;
vector<pair<int, int>> inspect;
bool Wall[MAX_N][MAX_N][MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];
bool tmp_visited[MAX_N][MAX_N][MAX_N][MAX_N];
int R, C, K, W;
pair<int, int> st_direction[] = { {0,1},{0,-1},{-1,0},{1,0} };
pair<int, int> dir[4][8] = { {{-1,1},{0,1},{1,1},{-1,0},{0,1},{0,1},{1,0},{0,1}}, {{1,-1},{0,-1},{-1,-1},{1,0},{0,-1},{0,-1},{-1,0},{0,-1}},{{-1,-1},{-1,0},{-1,1},{0, -1}, { -1,0 }, { -1,0 }, { 0,1 }, { -1,0 }}, { {1,1},{1,0},{1,-1},{0,1},{1,0},{1,0},{0,-1},{1,0}} };
 
void input();
void Wind(pair<int, int>, int);
bool is_ok(pair<int, int>);
bool check_temperature();
void Down_temp();
void Adjust_temp();
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    input();
    int Chocolate = 0;
    while (true) {
        for (int i = 0; i < Fan.size(); i++) {
            Wind(Fan[i].first, Fan[i].second);
        }
        Adjust_temp();
        Down_temp();
        Chocolate++;
        if (check_temperature())
            break;
        else if (Chocolate > 100)
            break;
    }
    cout << Chocolate << "\n";
    return 0;
}
 
void input() {
    cin >> R >> C >> K;
    for (int i = 1; i <= R; i++)
        for (int j = 1; j <= C; j++) {
            int num;
            cin >> num;
            if (num >= 1 && num <= 4) {
                Fan.push_back({ {i,j},num - 1 });
            }
            else if (num == 5)
                inspect.push_back({ i,j });
        }
 
    cin >> W;
    for (int i = 1; i <= W; i++) {
        int y, x, wall;
        cin >> y >> x >> wall;
        if (wall == 1) {
            Wall[y][x][y][x + 1] = true;
            Wall[y][x + 1][y][x] = true;
        }
        else if (wall == 0) {
            Wall[y][x][y - 1][x] = true;
            Wall[y - 1][x][y][x] = true;
        }
    }
}
 
void Wind(pair<int, int> st, int Direction) {
    queue < pair<pair<int, int>, int>> q;
    memset(visited, false, sizeof(visited));
    q.push({ {st.first + st_direction[Direction].first, st.second + st_direction[Direction].second}, 5 });
    while (!q.empty()) {
        pair<int, int> now = q.front().first;
        int strength = q.front().second;
        q.pop();
        if (visited[now.first][now.second])
            continue;
        visited[now.first][now.second] = true;
        Map[now.first][now.second] += strength;
        if (strength == 1)
            continue;
        for (int i = 0; i < 3; i++) {
            pair<int, int> next = { now.first + dir[Direction][i].first, now.second + dir[Direction][i].second };
            if (!is_ok(next))
                continue;
            if (visited[next.first][next.second])
                continue;
            if (i == 0) {
                pair<int, int> next_ = { now.first + dir[Direction][3].first, now.second + dir[Direction][3].second };
                if (Wall[now.first][now.second][next_.first][next_.second])
                    continue;
                if (Wall[next_.first][next_.second][next_.first + dir[Direction][4].first][next_.second + dir[Direction][4].second])
                    continue;
                q.push({ next, strength - 1 });
            }
            else if (i == 1) {
                pair<int, int> next_ = { now.first + dir[Direction][5].first, now.second + dir[Direction][5].second };
                if (Wall[now.first][now.second][next_.first][next_.second])
                    continue;
                q.push({ next,strength - 1 });
            }
            else if (i == 2) {
                pair<int, int> next_ = { now.first + dir[Direction][6].first, now.second + dir[Direction][6].second };
                if (Wall[now.first][now.second][next_.first][next_.second])
                    continue;
                if (Wall[next_.first][next_.second][next_.first + dir[Direction][7].first][next_.second + dir[Direction][7].second])
                    continue;
                q.push({ next, strength - 1 });
            }
        }
    }
}
 
bool is_ok(pair<int, int> pos) {
    if (pos.first < 1 || pos.first > R || pos.second < 1 || pos.second > C)
        return false;
    return true;
}
 
bool check_temperature() {
    for (int i = 0; i < inspect.size(); i++) {
        if (Map[inspect[i].first][inspect[i].second] < K)
            return false;
    }
    return true;
}
 
void Down_temp() {
    pair<int, int> direct[4] = { {0,1},{1,0},{0,-1},{-1,0} };
    pair<int, int> now = { 1,1 };
    for (int i = 0; i < 4; i++) {
        if (i % 2 == 0) {
            for (int j = 1; j < C; j++) {
                now = { now.first + direct[i].first, now.second + direct[i].second };
                if (Map[now.first][now.second])
                    Map[now.first][now.second]--;
            }
        }
        else {
            for (int j = 1; j < R; j++) {
                now = { now.first + direct[i].first, now.second + direct[i].second };
                if (Map[now.first][now.second])
                    Map[now.first][now.second]--;
            }
        }
    }
}
 
void Adjust_temp() {
    int temp[MAX_N][MAX_N];
    memset(temp, 0, sizeof(temp));
    memset(tmp_visited, false, sizeof(tmp_visited));
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            for (int k = 0; k < 4; k++) {
                pair<int, int> next = { i + st_direction[k].first, j + st_direction[k].second };
                if (!is_ok(next))
                    continue;
                if (Wall[i][j][next.first][next.second] || Wall[next.first][next.second][i][j])
                    continue;
                if (tmp_visited[i][j][next.first][next.second] || tmp_visited[next.first][next.second][i][j])
                    continue;
                tmp_visited[i][j][next.first][next.second] = true;
                tmp_visited[next.first][next.second][i][j] = true;
                int Value = (int)floor(abs(Map[next.first][next.second] - Map[i][j]) / 4);
                if (Value >= 1) {
                    if (Map[next.first][next.second] > Map[i][j]) {
                        temp[i][j] += Value;
                        temp[next.first][next.second] -= Value;
                    }
                    else {
                        temp[i][j] -= Value;
                        temp[next.first][next.second] += Value;
                    }
                }
            }
        }
    }
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++)
            Map[i][j] += temp[i][j];
    }
}

예제에서 테스트케이스를 대부분 온풍기의 위치를 같게 줘서 어디서 오류가 났는지 찾기가 어려웠다. 틀린 코드였는데도 우연히 예제는 다 맞게나왔었다.