[백준] 온풍기 안녕! (c++)

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

 

풀이 방법

시뮬레이션 문제이므로 조건 정리를 꼼꼼하게 하고 풀이하면 된다.

 

해당 문제에서 가장 까다로운 부분은 벽을 처리하는 것이다.

입력으로 주어지는 벽은 현재 칸에서 위 쪽에 있거나, 오른쪽에 있는데 이렇게 된다면 벽을 처리하기 위해 항상 해당 벽의 왼쪽 좌표나 아래쪽 좌표를 확인해야 한다는 불편함이 있다.

 

이를 해결하기 위해 입력을 받을 때 해당 벽의 양쪽 좌표에 벽을 표시해 주었다.

 

가령 a, b의 위쪽에 벽이 있다면, wall[a][b][2] = 1, wall [a-1][b][3] = 1로 y, x의 좌표에 dir (오른쪽, 왼쪽, 위쪽, 아래쪽)으로 설정해서 문제를 풀이하였다.

 

운풍기를 돌리기 위해 Fan 구조체를 정의하여, 온풍기의 좌표와 방향을 벡터에 저장해 두고 풀이하였다.

온풍기의 바람을 더해주기 위해 dfs를 사용하여, 방향에 맞는 좌표를 아래와 같이 저장해 두고 풀이하였다.

int dir_arr[4][3][2] = { // 오 왼 위 아래
    {{-1, 1}, {0, 1}, {1, 1}}, 
    {{-1, -1}, {0, -1}, {1, -1}},
    {{-1, -1}, {-1, 0}, {-1, 1}},
    {{1, -1}, {1, 0}, {1, 1}}
};

퍼질 수 있는 방향이다. dir_arr [a][b][c] == 온풍기의 바람이 a방향일 때, b번째(3개 중 하나)이고, c(y, x 좌표)이다.

 

check함수를 사용해서, 해당 방향으로 벽이 있는지 체크를 했다.

 

또한 온도 조절 과정은 완전 탐색을 하며, 계산한 값을 동시에 적용시키기 위해 벡터에 저장해 두고 모든 좌표의 계산이 끝나면 적용시켰다.

 

#include <iostream>
#include <vector>
#include <memory.h>
#include <algorithm>

using namespace std;
vector<pair<int, int> > check_area;
int wall[21][21][4];
int room[21][21];
int visited[21][21];
vector<int> spreed_temp[21][21];

struct Fan{
    int y, x, dir;

    Fan(int y, int x, int dir) : y(y), x(x), dir(dir) {}
};

vector<Fan> fans;
int n, m, k, w, eat = 0;
int dy[4] = {0, 0, -1, 1};
int dx[4] = {1, -1, 0 ,0};

int dir_arr[4][3][2] = { // 오 왼 위 아래
    {{-1, 1}, {0, 1}, {1, 1}}, 
    {{-1, -1}, {0, -1}, {1, -1}},
    {{-1, -1}, {-1, 0}, {-1, 1}},
    {{1, -1}, {1, 0}, {1, 1}}
};

// 오, 왼, 위, 아래 /// 위 -> 중간 -> 아래, // 왼쪽 -> 중간 -> 오른쪽
bool check(int y, int x, int dir, int idx) { // 진행 방향, i
    if (dir == 0) {
        if (idx == 0) {
            if (wall[y][x][2] == 0 && wall[y-1][x][0] == 0) return true; //
            else return false;
        }
        else if (idx == 1) {
            if (wall[y][x][0] == 0) return true;
            else return false;
        }
        else if (idx == 2) {
            if (wall[y][x][3] == 0 && wall[y+1][x][0] == 0) return true;
            else return false;
        }
    }

    else if (dir == 1) {
        if (idx == 0) {
            if (wall[y][x][2] == 0 && wall[y-1][x][1] == 0) return true;
            else return false;
        }
        else if (idx == 1) {
            if (wall[y][x][1] == 0) return true;
            else return false;
        }
        else if (idx == 2) {
            if (wall[y][x][3] == 0 && wall[y+1][x][1] == 0) return true;
            else return false;
        }
    }
    else if (dir == 2) {
        if (idx == 0) {
            if (wall[y][x][1] == 0 && wall[y][x-1][2] == 0) return true;
            else return false;
        }
        else if (idx == 1) {
            if (wall[y][x][2] == 0) return true;
            else return false;
        }
        else if (idx == 2) {
            if (wall[y][x][0] == 0 && wall[y][x+1][2] == 0) return true;
            else return false;
        }
    }
    else if (dir == 3) {
        if (idx == 0) {
            if (wall[y][x][1] == 0 && wall[y][x-1][3] == 0) return true;
            else return false;
        }
        else if (idx == 1) {
            if (wall[y][x][3] == 0) return true;
            else return false;
        }
        else if (idx == 2) {
            if (wall[y][x][0] == 0 && wall[y][x+1][3] == 0) return true;
            else return false;
        }
    }
}

void fill_room(int y, int x, int dir, int tem) {    
    visited[y][x] = 1;
    room[y][x] += tem;
    if (tem == 1) return ; //1 이면 확장 하지 않음
    if (dir == 0 || dir == 1) { // 오른쪽 왼쪽일 때 x좌표가 끝이면 확장 하지 않음
        if (x == 0 || x == m-1) return;
    }
    if (dir == 2 || dir == 3) { // 위 아래일 때 y좌표가 끝이면 확장하지 않음
        if (y == 0 || y == n-1) return ;
    }
    
    
    for (int i = 0;i < 3;i++) {
        int ny = y + dir_arr[dir][i][0];
        int nx = x + dir_arr[dir][i][1];

        if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
        if (visited[ny][nx] == 1) continue;
        // 벽 처리
        if (check(y, x, dir, i)) {            
            fill_room(ny, nx, dir, tem-1);
        }                
    }
    return ;
}

void on_fan() {
    for (int i = 0;i < fans.size();i++) {
        memset(visited, 0, sizeof(visited));
        int dir = fans[i].dir;
        fill_room(fans[i].y + dir_arr[dir][1][0], fans[i].x + dir_arr[dir][1][1], fans[i].dir, 5);
    }
}

void spreed() {    
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            for (int k = 0;k < 4;k++) {
                if (wall[i][j][k] == 1) continue; // 벽에 막히면 pass
                int ny = i + dy[k];
                int nx = j + dx[k];
                if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
                int temp = abs(room[i][j] - room[ny][nx]) / 4;
                if (room[i][j] > room[ny][nx]) {
                    spreed_temp[i][j].push_back(-temp); // 동시에 적용시키기 위해 저장
                }
                else spreed_temp[i][j].push_back(temp);
            }
        }
    }

    for (int i = 0;i < n;i++) { // 저장해 둔 것을 적용
        for (int j = 0;j < m;j++) {
            for (int k = 0;k < spreed_temp[i][j].size();k++) {
                room[i][j] += spreed_temp[i][j][k];
            }            
            spreed_temp[i][j].clear();
        }        
    }
}

void minus_outline() { // 테두리 -1하기
    for (int j = 0; j < m; j++) {
        if (room[0][j] != 0)
            room[0][j]--;
    }
 
    for (int i = 1; i < n; i++) {
        if (room[i][m-1] != 0)
            room[i][m-1]--;
    }

    for (int j = 0; j < m - 1;j++) {
        if (room[n-1][j] != 0)
            room[n-1][j]--;
    }

    for (int i = 1;i < n-1;i++) {
        if (room[i][0] != 0)
            room[i][0]--;
    }


}

bool check_temperature() { // 종료 조건 탐색
    for (int i = 0; i < check_area.size();i++) {
        if (room[check_area[i].first][check_area[i].second] < k) return false;
    }
    
    return true;
}
void print_room() {
    cout << endl;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            cout << room[i][j] << " ";
        }
        cout << endl;
    }
}
int main() {
    cin >> n >> m >> k;

    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            cin >> room[i][j];            
            if (room[i][j] == 1) fans.push_back(Fan(i, j, 0));
            if (room[i][j] == 2) fans.push_back(Fan(i, j, 1));
            if (room[i][j] == 3) fans.push_back(Fan(i, j, 2));
            if (room[i][j] == 4) fans.push_back(Fan(i, j, 3));
            if (room[i][j] == 5) check_area.push_back(make_pair(i, j));
            room[i][j] = 0; // 초기화
        }
    }
    

    cin >> w;
    int a, b, c;
    for (int i = 0;i < w;i++) { // 0 은 위, 1은 오른 쪽, // 오 왼 위 아래
        cin >> a >> b >> c;
        if (c == 0) {
            wall[a-1][b-1][2] = 1;
            wall[a-2][b-1][3] = 1;
        }
        if (c == 1) {
            wall[a-1][b-1][0] = 1;
            wall[a-1][b][1] = 1;
        }        
    }

    while(eat < 101) {
        on_fan();
        // print_room();
        spreed();
        minus_outline();
        eat++;
        if (check_temperature()) break;        
    }

    cout << eat;

    return 0;
}