[BFS] 백준 23289 온풍기 안녕! C++

 

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

23289번: 온풍기 안녕!

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Position {
    int x, y, dir;
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int r, c, k, w;
    int dy[4] = {1, 0, -1, 0}; // 열
    int dx[4] = {0, 1, 0, -1}; // 행 
    int check[3] = {0, 1, 3}; // 확인해야 할 방향 

    cin >> r >> c >> k;

    vector<vector<int>> board(r, vector<int>(c, 0));
    vector<Position> fan;
    vector<vector<vector<bool>>> wall(4, vector<vector<bool>>(r, vector<bool>(c, false)));
    vector<pair<int, int>> place;

    int num;
    for(int i=0; i<r; i++) {
        for(int j=0; j<c; j++) {
            cin >> num; 
            if (num == 5) place.push_back({i, j});

            // 우좌상하 -> 우하좌상(시계방향)
            else if (num == 4) fan.push_back({i, j, 1});
            else if (num == 3) fan.push_back({i, j, 3});
            else if (num == 2) fan.push_back({i, j, 2});
            else if (num == 1) fan.push_back({i, j, 0});
        }
    }

    cin >> w;

    int x, y, t;
    for(int i=0; i<w; i++) {
        cin >> x >> y >> t;
        x--; y--;
        if (t == 0) { // 방향별 저장
            wall[3][x][y] = true;
            wall[1][x-1][y] = true;
        }
        else {
            wall[0][x][y] = true;
            wall[2][x][y+1] = true;
        }
    }

    int answer = 0;
    while (true) {
        // 1. 온풍기 바람
        for(int i=0; i<fan.size(); i++) {
            int d = fan[i].dir;
            int x = fan[i].x + dx[d];
            int y = fan[i].y + dy[d];
            board[x][y] += 5;

            queue<pair<Position, int>> q;
            vector<vector<bool>> visited(r, vector<bool>(c, false)); // 중복 제외
            q.push({{x, y, d}, 5});
            visited[x][y] = true;

            while(!q.empty()) {
                Position p = q.front().first;
                int degree = q.front().second - 1;
                q.pop();
                if (degree == 0) continue;

                for(int j=0; j<3; j++) {
                    int x = p.x;
                    int y = p.y;
                    int d = (p.dir + check[j]) % 4;
                    if (wall[d][x][y]) continue; // 벽 확인

                    int cx = (j == 0)? 0 : dx[d];
                    int cy = (j == 0)? 0 : dy[d];
                    x += cx;
                    y += cy;
                    if ((x < 0) || (y < 0) || (x >= r) || (y >= c)) continue;
                    if (wall[p.dir][x][y]) continue; // 좌우만 벽 확인

                    x += dx[p.dir];
                    y += dy[p.dir];
                    if ((x < 0) || (y < 0) || (x >= r) || (y >= c)) continue;
                    if (visited[x][y]) continue;

                    visited[x][y] = true;
                    board[x][y] += degree;
                    q.push({{x, y, p.dir}, degree});
                }
            }
        }

        // 2. 온도 조절
        vector<vector<int>> change(r, vector<int>(c, 0)); // 동시 변경
        for(int i=0; i<r; i++) {
            for(int j=0; j<c; j++) {
                for(int d=0; d<4; d++) {
                    if (wall[d][i][j]) continue; // 벽 확인

                    int x = i + dx[d];
                    int y = j + dy[d];
                    if ((x < 0) || (y < 0) || (x >= r) || (y >= c)) continue;
                    if (board[i][j] <= board[x][y]) continue; // 높 -> 낮

                    int diff = (board[i][j] - board[x][y]) / 4; // 차이
                    change[i][j] -= diff;
                    change[x][y] += diff;
                }
            }
        }
        
        for(int i=0; i<r; i++) {
            for(int j=0; j<c; j++)
                board[i][j] += change[i][j];
        }

        // 3. 가장 바깥쪽 칸 온도 1씩 감소
        for(int i=0; i<r; i++) {
            if (board[i][0] > 0) board[i][0]--;
            if (board[i][c-1] > 0) board[i][c-1]--;
        }

        for(int i=1; i<c-1; i++) { // 모서리 주의
            if (board[0][i] > 0) board[0][i]--;
            if (board[r-1][i] > 0) board[r-1][i]--;
        }

        // 4. 초콜릿 먹기
        answer++;
        if (answer > 100) break; // 초콜릿 100개 초과
        
        // 5.온도 K 이상 검사
        int flag = true;
        for(int i=0; i<place.size(); i++) {
            if (board[place[i].first][place[i].second] < k) {
                flag = false;
                break;
            }
        }
        if (flag) break; // 모든 온도 K 이상
    }

    cout << answer;

    return 0;
}