23289. 온풍기 안녕!

문제 링크

23289번: 온풍기 안녕!

풀이

지문이 몹시 길고 복잡하지만, 천천히 읽으면서 기능을 하나씩 구현해나가면 충분히 풀 수 있다.

문제에서 난관은 아마 바람이 나올 때 벽에 가로막히는 것에 대한 처리와 온도 조절일 것이다. 필자는 주어진 공간을 세 개의 2차원 배열로 나누어서 풀었다.

• 각 칸의 온도를 저장하는 배열 board
• 각 칸의 위쪽에 벽이 있는지를 저장하는 배열 hWall
• 각 칸의 오른쪽에 벽이 있는지를 저장하는 배열 vWall

이렇게 하면 바람의 온도 확산에 대해서 BFS를 실행할 때에도 효율적으로 벽의 위치를 참조할 수 있다.

온도 조절의 경우, 각 칸의 아래쪽과 오른쪽 칸에 대해서만 온도 조절을 실행하고, 이것을  왼쪽 위 칸부터 오른쪽 아래까지 반복문을 돌리면서 실행하였다. 왼쪽 위부터 오른쪽 아래 순서로 반복문을 돌리면, 이미 지나간 왼쪽과 위쪽 칸은 온도 조절이 끝났으므로 오른쪽과 아래쪽만 온도 조절을 실행하면 되는 것이다.

 

그 외의 팁이라면, 문제에서 주어진 5가지 과정을 함수로 모듈화해서 구현하면 효율적으로 코드를 짤 수 있다. 아니, 아직 이렇게 짜는 게 익숙하지 않은 사람이라면 지금이라도 습관 들이기를 권장한다.

이런 구현 문제들은 보통 어떤 절차가 주어지고 그대로 시뮬레이션해서 결과를 출력하라는 식인데, 초보자들은 이 절차에 대한 코드를 함수 한두 개에 몰아서 짜곤 한다. 그런데 이렇게 짜게 되면 나중에 코드가 길어질 때 내가 어떤 기능을 어디에 구현했고, 이 변수는 왜 선언했는지 등을 스스로 알기 힘들어진다. 어차피 이 문제에서만 쓸 코드고, 그런 식으로 짜서 1트만에 AC 받는 능력자라면 할 말 없지만, 대다수는 그렇지 않다. 만약 짠 코드가 틀려서 고쳐야 한다면, 그때부터 자기가 깊게 판 무덤을 메워야 하는 상황이 벌어진다.

필자도 초보자 시절 처음 구현문제를 풀 때에는 아무 생각 없이 main 함수에 모든 기능을 때려박곤 했다. 이게 하위 티어 문제라면 좀 불편한 정도였지만, 골드 3 즈음부터는 좀만 구현한다 싶으면 코드가 100줄은 그냥 넘어가는 것이 아닌가. 당연히 그 코드에는 기능 구현할 때마다 그때그때 선언해 놓은 변수들이 곳곳에 산재해 있었고, WA를 받을 때마다 디버깅의 지옥을 맛봐야 했다. 지금은 모든 문제를 풀 때마다 모듈화를 하는 건 아니지만, 적어도 복잡한 구현문제에는 모듈화를 하는 습관을 들이고 있다. 덕분에 예전보다 디버깅할 때 변수의 위치, 기능을 곧바로 알 수 있어서 한결 편해졌다.

그러니 지금이라도 코드 정리하는 습관은 가져놓도록 하자. 중요한 기능은 함수로 모듈화하는 습관, 변수, 함수명은 무슨 역할인지 알기 쉽게 짓는 습관 등등. 현업에서는 여러 사람들이랑 같은 코드 갖고 작업해야 할 텐데, 상대도 알아보기 쉽도록 깔끔하게 코딩하는 습관을 가지는 게 좋지 않겠는가? 변수명 지으면서 영어 실력도 쌓을 수 있고

시간 복잡도

일단 공간의 칸 수가 \(RC\)이니, 온풍기와 조사하는 칸 각각의 최대 가능한 개수 역시 \(RC\)이다. 이때 각 과정의 시간 복잡도를 따져보자면

1. 집에 있는 모든 온풍기에서 바람이 한 번 나옴: \(O(25RC)=O(RC)\)
2. 온도가 조절됨: \(O(RC)\)
3. 온도가 1 이상인 가장 바깥쪽 칸의 온도가 1씩 감소: \(O(2(R+C))=O(R+C)\)
4. 초콜릿 먹기: \(O(1)\)
5. 조사하는 모든 칸의 온도가 K 이상이 되었는지 검사: \(O(RC)\)

이를 종합하면 총 시간 복잡도는 \(O(RC)\)이다.

소스코드

#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
#define RIGHT    1
#define LEFT    5
#define UP    7
#define DOWN    3
using namespace std;

int R, C, K, W, x, y, t;
int board[20][20];
int visit[20][20];
int temptemp[20][20];
bool vWall[20][20], hWall[20][20];
vector<pair<pair<int, int>, int>> heater;
vector<pair<int, int>> examineCell;
int dx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
int dy[] = { 1, 1, 1, 0, -1, -1, -1, 0 };
int didx[] = { 0, RIGHT, LEFT, UP, DOWN };

bool validRange(int x, int y) {
    return x >= 0 && x < R && y >= 0 && y < C;
}

bool isBlocked(int x, int y, int dir, int route) {
    if (dir == RIGHT) {
        if (route == 0 && vWall[x][y]) return true;
        if (route == -1 && (hWall[x][y] || vWall[x - 1][y])) return true;
        if (route == 1 && (hWall[x + 1][y] || vWall[x + 1][y])) return true;
    }

    if (dir == LEFT) {
        if (route == 0 && vWall[x][y - 1]) return true;
        if (route == -1 && (hWall[x + 1][y] || vWall[x + 1][y - 1])) return true;
        if (route == 1 && (hWall[x][y] || vWall[x - 1][y - 1])) return true;
    }

    if (dir == UP) {
        if (route == 0 && hWall[x][y]) return true;
        if (route == -1 && (vWall[x][y - 1] || hWall[x][y - 1])) return true;
        if (route == 1 && (vWall[x][y] || hWall[x][y + 1])) return true;
    }

    if (dir == DOWN) {
        if (route == 0 && hWall[x + 1][y]) return true;
        if (route == -1 && (vWall[x][y] || hWall[x + 1][y + 1])) return true;
        if (route == 1 && (vWall[x][y - 1] || hWall[x + 1][y - 1])) return true;
    }

    return false;
}

void bfs(int x, int y, int dir) {
    queue<pair<int, int>> q;
    memset(visit, 0, sizeof(visit));
    int idx = didx[dir];
    q.emplace(x + dx[idx], y + dy[idx]);
    visit[x + dx[idx]][y + dy[idx]] = 5;
    board[x + dx[idx]][y + dy[idx]] += visit[x + dx[idx]][y + dy[idx]];

    while (!q.empty()) {
        int curx = q.front().first;
        int cury = q.front().second;
        q.pop();
        if (visit[curx][cury] == 1) continue;

        for (int i = -1; i <= 1; ++i) {
            int nx = curx + dx[(idx + i) % 8];
            int ny = cury + dy[(idx + i) % 8];
            if (!validRange(nx, ny) || visit[nx][ny]) continue;
            if (isBlocked(curx, cury, idx, i)) continue;

            visit[nx][ny] = visit[curx][cury] - 1;
            board[nx][ny] += visit[nx][ny];
            q.emplace(nx, ny);
        }
    }
}

void spreadWind() {
    for (auto h : heater) {
        bfs(h.first.first, h.first.second, h.second);
    }
}

void adjustTemp() {
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            if (i < R - 1 && !hWall[i + 1][j]) {
                temptemp[i][j] += ((board[i + 1][j] - board[i][j]) / 4);
                temptemp[i + 1][j] += ((board[i][j] - board[i + 1][j]) / 4);
            }

            if (j < C - 1 && !vWall[i][j]) {
                temptemp[i][j] += ((board[i][j + 1] - board[i][j]) / 4);
                temptemp[i][j + 1] += ((board[i][j] - board[i][j + 1]) / 4);
            }

			board[i][j] += temptemp[i][j];
			temptemp[i][j] = 0;
        }
    }
}

void decreaseBorderTemp() {
    for (int i = 0; i < C; ++i) {
        board[0][i] -= (board[0][i] ? 1 : 0);
        board[R - 1][i] -= (board[R - 1][i] ? 1 : 0);
    }

    for (int i = 1; i < R - 1; ++i) {
        board[i][0] -= (board[i][0] ? 1 : 0);
        board[i][C - 1] -= (board[i][C - 1] ? 1 : 0);
    }
}

bool examineTemp() {
    for (auto p : examineCell) {
        if (board[p.first][p.second] < K) return false;
    }

    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> R >> C >> K;
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            cin >> board[i][j];
            if (board[i][j] == 5) {
                examineCell.emplace_back(i, j);
                board[i][j] = 0;
            }
            else if (board[i][j] > 0) {
                heater.emplace_back(make_pair(i, j), board[i][j]);
                board[i][j] = 0;
            }
        }
    }

    cin >> W;
    while (W--) {
        cin >> x >> y >> t;
        if (t) {
            vWall[x - 1][y - 1] = true;
        }
        else {
            hWall[x - 1][y - 1] = true;
        }
    }

    int cnt = 0;
    while (cnt <= 100) {
        spreadWind();
        adjustTemp();
        decreaseBorderTemp();
        ++cnt;
        if (examineTemp()) break;
    }

    cout << cnt;
    return 0;
}