[백준] 23289: 온풍기 안녕!(C++, 하드코딩 적은 풀이)

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

23289번: 온풍기 안녕!

상어 시리즈의 맥을 끊어버리는 안녕! 시리즈입니다.

 

소요 시간

중간에 일이 생겨서 시간을 정확히 재지는 못했지만 2시간 가량 걸린 것 같습니다.

미세먼지 안녕!과 비교해 보면 확산이 일어난다는 점이 비슷합니다.

그리고 미세먼지 안녕!은 골드였던 것 같은데 이 문제는 플래티넘 문제로 더 어려운 문제입니다. 실제로 구현할 것도 많았습니다.

핵심은 "벽" 입니다.

 

문제 평가

Solve.ac 의 사용자 기여 내용을 바탕으로 대부분이 이 문제를 어떻게 평가하고 있는지 봤습니다.

전체적으로 구현할 것이 많다, 벽 때문에 구현이 어렵다, 양이 많아 실수하면 디버깅 지옥으로 떨어진다 같은 의견들이 있었습니다.

탈모가 왔다, 흰머리가 났다, 온풍기 틀지 마라 등의 의견도 있었습니다. 큐빙 이라는 문제와 비슷하거나 좀 더 쉽다는 반응도 있었습니다.

저도 풀면서 이 문제는 하드코딩이 필요한 부분들이 있어 깔끔하지 못하고, 귀찮고, 구현할 양이 많은 삼박자를 모두 갖춘 문제라는 생각이 들었습니다. 그래도 이런 문제를 많이 풀어 봐야 실력이 오를 것 같아서 앞으로는 구현, 시뮬레이션 문제는 플레 문제로 많이 풀어보려구 합니다.

 

구상

1. 뜨거운 바람을 퍼트리는 함수

2. 온도 조절되는 함수

3. 온도 1 감소하는 함수 + 초콜릿 먹기

4. 온도 측정하는 함수

 

나머지는 시키는 대로 하면 되는데, 1번이 좀 복잡합니다. 벽이 있으면 거기로는 바람이 갈 수 없는데, "벽이 있다"의 조건이 좀 까다롭습니다. 이 조건을 또 방향마다 다르게 해야 하기 때문에 열이 받았습니다.

 

벽이 있다의 조건

방향마다 체크해야 할 벽이 달라집니다. 이걸 다 다르게 하드코딩하는게 너무 싫어서 일반화 해보려고 했는데 어려웠습니다. 인터넷을 찾아봐도 거의 다들 하드코딩으로 해결하시는것 같았습니다.

전체 방향에 대한 일반화를 할 수가 없어서 오른쪽&왼쪽, 위쪽&아래쪽 정도로 일반화해서 깔끔하게 구현하려고 노력했습니다.

 

(1) 방향이 오른쪽, 왼쪽인 경우(모든 dx, dy에 대해)

- (x,y)와 (x+dx, y) 사이, (x+dx, y)와 (x+dx, y+dy) 사이에 벽이 있으면 안된다.

 

(2) 방향이 위쪽, 아래쪽인 경우(모든 dx, dy에 대해)

- (x,y)와 (x, y+dy) 사이, (x, y+dy)와 (x+dx, y+dy) 사이에 벽이 있으면 안된다.

 

바람이 오른쪽으로 불 때 (x, y) -> (x, y+1) 같은 경우에는 벽이 있을 조건이 하나인데 두개를 확인하고 있습니다. 이 때는 어차피 dx가 0이어서 (1) 첫번째 조건이 (x,y)와 (x,y) 사이가 되고, 여기에 벽이 있을 리가 없기 때문에 이 경우 첫번째 조건은 없는 조건이나 마찬가집니다.

 

더 깔끔한 방법이 있으면 꼭 말해 주세요.

 

+) 저는 벽을 pair의 집합으로 저장했고, (칸1 좌표 1차원 변환값, 칸2 좌표 1차원 변환값)이랑 (칸2 좌표 1차원 변환값, 칸1 좌표 1차원 변환값) 이렇게 저장해서 찾기 쉽게 했습니다.

 

코드 (모든 좌표값은 1차원 정수로 변환되어 있습니다.)

#include <string>
#include <vector>
#include<iostream>
#include <climits>
#include<set>
#include<cmath>
#include<algorithm>

using namespace std;

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

int ddx[4] = {0,0,1,-1};
int ddy[4] = {1,-1,0,0};

bool check_path(int xy, int nx, int ny, int d, int r, int c, set<pair<int, int> >& wall) {
    if(nx < 0 || nx > r-1 || ny < 0 || ny > c-1) return false;
    if(d==1 || d==2) {
        int y = xy%c;
        if(wall.find(pair<int, int>(xy, nx*c+y)) == wall.end() && 
            wall.find(pair<int, int>(nx*c+y, nx*c+ny)) == wall.end()) {
                return true;
        }
    }
    else {
        int x = xy/c;
        if(wall.find(pair<int, int>(xy, x*c+ny)) == wall.end() && 
            wall.find(pair<int, int>(x*c+ny, nx*c+ny)) == wall.end()) {
                return true;
        }
    }
    return false;
}

void make_wind(int r, int c, int d, int R, int C, vector<vector<int> >& tem, set<pair<int, int> >& wall) {
    vector<vector<int> > add;
    add.resize(R);
    for(int i=0; i<R; i++) {
        add[i].resize(C);
        fill_n(add[i].begin(), C, 0);
    }
    
    vector<int> next;
    if(d == 1) 
        next.push_back(r*C + c + 1);
    else if(d == 2)
        next.push_back(r*C + c - 1);
    else if(d == 3)
        next.push_back((r-1)*C + c);
    else if(d == 4)
        next.push_back((r+1)*C + c);
    for(int i=5; i>0; i--) {
        vector<int> prev_next = next;
        next.clear();
        for(int j=0; j<prev_next.size(); j++) {
            int xy = prev_next[j];
            int x = xy/C; int y = xy%C;
            add[x][y] = i; 
            for(int k=0; k<3; k++) {
                int nx = x + dx[d][k]; int ny = y + dy[d][k];
                if(check_path(xy, nx, ny, d, R, C, wall)) 
                    next.push_back(nx*C + ny);
            }
        }
    }

    for(int i=0; i<R; i++) {
        for(int j=0; j<C; j++) {
            tem[i][j] += add[i][j];
        }
    }
}

void adjust_tem(int r, int c, vector<vector<int> >& tem, set<pair<int, int> >& wall) {
    vector<vector<int> > add;
    bool visited[r][c];
    add.resize(r);
    for(int i=0; i<r; i++) {
        add[i].resize(c);
        fill_n(visited[i], c, false);
    }
    
    for(int i=0; i<r; i++) {
        for(int j=0; j<c; j++) {
            for(int k=0; k<4; k++) {
                //상하좌우 인접
                int nx = i + ddx[k]; int ny = j + ddy[k];
                if(nx <0 || nx > r-1 || ny < 0 || ny > c-1 || visited[nx][ny]) continue;
                if(wall.find(pair<int, int>(i*c+j, nx*c+ny)) != wall.end()) continue;
                if(tem[i][j] > tem[nx][ny]) {
                    int delta = (tem[i][j] - tem[nx][ny])/4;
                    add[i][j] -= delta;
                    add[nx][ny] += delta;
                }
                else if(tem[i][j] < tem[nx][ny]) {
                    int delta = (tem[nx][ny] - tem[i][j])/4;
                    add[i][j] += delta;
                    add[nx][ny] -= delta;
                }
            }
            visited[i][j] = true;
        }
    }
    for(int i=0; i<r; i++) {
        for(int j=0; j<c; j++) {
            tem[i][j] += add[i][j];
        }
    }
}

void reduce_tem(int r, int c, vector<vector<int> >& tem) {
    for(int i=0; i<c-1; i++) {
        if(tem[0][i] > 0) tem[0][i] -= 1;
    }
    for(int i=0; i<r-1; i++) {
        if(tem[i][c-1] > 0) tem[i][c-1] -= 1;
    }
    for(int i=c-1; i>0; i--) {
        if(tem[r-1][i] > 0) tem[r-1][i] -= 1;
    }
    for(int i=r-1; i>0; i--) {
        if(tem[i][0] > 0) tem[i][0] -= 1;
    }
}

bool check_tem(int r, int c, int k, vector<vector<int> >& tem, vector<vector<int> >& room) {
    for(int i=0; i<r; i++) {
        for(int j=0; j<c; j++) {
            if(room[i][j] == 5) {
                if(tem[i][j] < k) {
                    return false;
                }
            }
        }
    }
    return true;
}

int solution(int r, int c, int k, int w, vector<vector<int> >& room, set<pair<int, int> >& wall) {
    int choco = 0;
    vector<vector<int> > tem;
    tem.resize(r);
    for(int i=0; i<r; i++) {
        tem[i].resize(c);
    }

    while(choco <= 100) {
        for(int i=0; i<r; i++) {
            for(int j=0; j<c; j++) {
                if(room[i][j] != 0 && room[i][j] != 5) {
                    make_wind(i, j, room[i][j], r, c, tem, wall);
                }
            }
        }

        adjust_tem(r, c, tem, wall);
        reduce_tem(r, c, tem);
        choco += 1;
        if(check_tem(r, c, k, tem, room)) break;
    }
    return choco;

}

int main(int argc, char** argv)
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int r, c, k;
    cin >> r >> c >> k;
    vector<vector<int> > room;
    for(int i=0; i<r; i++) {
        vector<int> row;
        for(int j=0; j<c; j++) {
            int a; cin >> a;
            row.push_back(a);
        }
        room.push_back(row);
    }
    int w;
    cin >> w;
    set<pair<int, int> > wall; // first, second 사이에 벽이 있다는 뜻
    for(int i=0; i<w; i++) {
        int x, y, t;
        cin >> x >> y >> t;
        x -= 1; y -= 1; //0,0 sync
        if(t == 1) {
            wall.insert(pair<int, int>(x*c + y, x*c + y+1));
            wall.insert(pair<int, int>(x*c + y+1, x*c + y));
        }
        else {
            wall.insert(pair<int, int>(x*c + y, (x-1)*c + y));
            wall.insert(pair<int, int>((x-1)*c + y, x*c + y));
        }
    }
    cout << solution(r, c, k, w, room, wall) << endl;


    return 0;
}