미세먼지 안녕! 골드 4

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

문제 읽고, 생각해보기

문제를 읽어보다면, 특별한 점은 기존의 BFS에 공기 청정기가 하나 추가되고, 배열 내 값이 이동한다는 점이다.

해당 사항의 대해 순서대로 어떻게 진행되는지도 친절하게 되어 있다.

해당 문제에서 요구하는 기술은 BFS와 배열 회전이라고 생각된다.

다만 해당 글을 쓰는 이유는 그 2가지를 제대로 못해서, 참회하고자, 기억하고자 적는다.

먼저 문제에서는 공기 청정기에 대한 정의가 있다.

공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다.

해당 내용을 통해 이후 회전 방법에 대해 고민될 부분이 조금 적어진다.

그 다음은 미세먼지가 확산되는 방법은 기존 토마토? 관련되어 비슷하니 넘어가도 좋을 것 같다.(어차피 아래에서 설명할 예정)

문제 풀이

BFS라고 해서 큐를 무조건 써야 하는 건 아니다.

먼저 문제에서 BFS라는 점을 주었기 때문에 공기 청정기 가동되는 부분을 제외하고 동일하게 풀어도 된다는 생각이 들어서 그렇기 풀게 된다면 이런 생각이 들 수 있다.

BFS -> 큐가 필요하다. -> 큐에 T초를 구분하기 위해서 값을 어떻게 넣지?

 왜 그렇냐면 문제 정의에 따르면, 1초 돌고 공기 청정기가 돌아야 하니 큐에 넣은 값으로 한번 탐색을 멈춰야 하기 때문이다. 어떻게 할 수 있을까?

다른 문제를 조금 풀어보았다면, 구분하기 위해서 큐 요소에 초를 넣는 행위를 하지 않을까 싶다. 나도 그렇게 생각했다. 다음 초가 된 경우 break를 하지 않을까?

나는 그게 싫어서 큐를 하나 만들어서 다음 요소를 들을 담아두었다.

 그런데 그럴 필요가 없었다. 미세먼지를 찾아서 확산만 하면 된다. 그러니까 미로 찾기? 길 찾기? 단축 경로 찾기 등이 아니다. 그러니까 미세먼지만 찾아서 확장시켜주면 된다.

배열 회전은 거꾸로

배열 회전에서도 그림에 그려진 방향대로 하니, 각 마지막 요소를 어떻게 덮어쓰기를 해줄지 고민이었는데, 거꾸로 하면 그런 문제가 해소되는 것이었다... 

#include <iostream>
#include <vector>
using namespace std;

int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };

// 상단 공기청정기 순환
void rotateTop(vector<vector<int>>& board, int top, int cols) {
    // 왼쪽 세로
    for (int i = top - 1; i > 0; --i) {
        board[i][0] = board[i - 1][0];
    }
    // 위쪽 가로
    for (int j = 0; j < cols - 1; ++j) {
        board[0][j] = board[0][j + 1];
    }
    // 오른쪽 세로
    for (int i = 0; i < top; ++i) {
        board[i][cols - 1] = board[i + 1][cols - 1];
    }
    // 아래쪽 가로
    for (int j = cols - 1; j > 1; --j) {
        board[top][j] = board[top][j - 1];
    }
    board[top][1] = 0; // 공기청정기에서 나온 공기
}

// 하단 공기청정기 순환
void rotateBottom(vector<vector<int>>& board, int bottom, int cols, int rows) {
    // 왼쪽 세로
    for (int i = bottom + 1; i < rows - 1; ++i) {
        board[i][0] = board[i + 1][0];
    }
    // 아래쪽 가로
    for (int j = 0; j < cols - 1; ++j) {
        board[rows - 1][j] = board[rows - 1][j + 1];
    }
    // 오른쪽 세로
    for (int i = rows - 1; i > bottom; --i) {
        board[i][cols - 1] = board[i - 1][cols - 1];
    }
    // 위쪽 가로
    for (int j = cols - 1; j > 1; --j) {
        board[bottom][j] = board[bottom][j - 1];
    }
    board[bottom][1] = 0; // 공기청정기에서 나온 공기
}

int main() {
    int r, c, t;
    cin >> r >> c >> t;

    vector<vector<int>> board(r, vector<int>(c, 0));
    pair<int, int> upAir = { -1, -1 }, downAir;

    // 입력 처리 및 공기청정기 위치 확인
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> board[i][j];
            if (board[i][j] == -1) {
                if (upAir.first == -1) {
                    upAir = { i, j };
                }
                else {
                    downAir = { i, j };
                }
            }
        }
    }

    while (t--) {
        // 1. 미세먼지 확산
        vector<vector<int>> temp(r, vector<int>(c, 0)); // 확산 결과 저장
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (board[i][j] > 0) {
                    int spreadAmount = board[i][j] / 5;
                    int spreadCount = 0;

                    for (int k = 0; k < 4; k++) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];
                        if (nx >= 0 && ny >= 0 && nx < r && ny < c && board[nx][ny] != -1) {
                            temp[nx][ny] += spreadAmount;
                            spreadCount++;
                        }
                    }
                    temp[i][j] += board[i][j] - (spreadAmount * spreadCount);
                }
            }
        }
        board = temp;

        // 2. 공기청정기 작동
        rotateTop(board, upAir.first, c);
        rotateBottom(board, downAir.first, c, r);

        // 공기청정기 위치 값 유지
        board[upAir.first][0] = -1;
        board[downAir.first][0] = -1;
    }

    // 최종 출력
    int result = 0;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (board[i][j] > 0) {
                result += board[i][j];
            }
        }
    }
    cout << result << "\n";
    return 0;
}