백준 17144번 - 미세먼지 안녕!

백준 17144번 - 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

이 문제는 시뮬레이션 문제이다.

문제의 정답률이 높길래 쉬울 거라 생각했는데 생각보다 오래 걸렸다.

문제를 풀면서 가장 기억에 남는 실수 두 가지는

 

1. 확산은 동시에 된다.

2. 바람이 부는 것을 구현할 때 끝에서부터? 시작해야 한다.

 

쉽게 말하면 아래의 코드는 왼쪽에서 오른쪽으로 바람이 부는 코드인데,

왼쪽부터 시작하지 않고 오른쪽 끝부터 시작한다. 

#include <iostream>
 
for (int i = c - 1; i >= 1; i--) {
    if (i == c - 1)last_1 = map[n][c - 1];
    if (map[n][i - 1] == -1) map[n][i] = 0;
    else if (map[n][i] == -1) continue;
    else map[n][i] = map[n][i - 1];
}

다른 사람들은 어떻게 짠지 모르겠지만 내 코드는 확산할 때는 다른 배열에 확산시키고 다시 더했다.

또 단순하게 흐르는 방향대로 차근차근 구현해 보니 코드가 엄청 길게 짜졌다.

바람의 이동 코드를 줄일 수 있다면 좀 줄여보고 싶네..

 

#include <iostream>
#pragma warning(disable:4996)
using namespace std;
 
int r, c, t;
int map[51][51];
int ano[51][51];
bool check[51][51];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
pair<pair<int, int>, pair<int, int>> air_ref;
 
void spread() {
    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++) {
            if (map[i][j] > 0) {
                int cnt = 0;
                for (int k = 0; k < 4; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if (0 <= nx && nx < r && 0 <= ny && ny < c) {
                        if (map[nx][ny] != -1) {
                            ano[nx][ny] += map[i][j] / 5;
                            cnt++;
                        }
                    }
                }
                map[i][j] -= ((map[i][j] / 5) * cnt);
            }
        }
    }
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (ano[i][j] > 0) {
                map[i][j] += ano[i][j];
                ano[i][j] = 0;
            }
        }
    }
}
 
void circulate() {
    int n, m, last_1, last_2;
    n = air_ref.first.first;
    m = air_ref.first.second;
    //공기청정기 위쪽
    //오른쪽 이동
    for (int i = c - 1; i >= 1; i--) {
        if (i == c - 1)last_1 = map[n][c - 1];
        if (map[n][i - 1] == -1) map[n][i] = 0;
        else if (map[n][i] == -1) continue;
        else map[n][i] = map[n][i - 1];
    }
    //위쪽 이동
    for (int i = 0; i < n; i++) {
        if (i == 0)last_2 = map[i][c - 1];
        if (i == n - 1) {
            if (map[i][c - 1] != -1) map[i][c - 1] = last_1;
            continue;
        }
        if (map[i + 1][c - 1] == -1) {
            if (map[i][c - 1] == -1) continue;
            map[i][c - 1] = 0;
        }
        else map[i][c - 1] = map[i + 1][c - 1];
    }
    //왼쪽 이동
    for (int i = 0; i < c - 1; i++) {
        if (i == 0)last_1 = map[0][0];
        if (i == c - 2) {
            if (map[0][i] != -1 && map[0][c - 1] != -1) map[0][i] = last_2;
            else if (map[0][c - 1] == -1)map[0][i] = 0;
            continue;
        }
        if (map[0][i + 1] == -1) map[0][i] = 0;
        else if (map[0][i] == -1) continue;
        else map[0][i] = map[0][i + 1];
    }
    //아래 이동
    for (int i = n; i > 0; i--) {
        if (i == 1) {
            if (map[i][0] != -1) map[i][0] = last_1;
            continue;
        }
        if (map[i - 1][0] == -1) {
            if (map[i][0] == -1) continue;
            map[i][0] = 0;
        }
        else if (map[i][0] == -1) continue;
        else map[i][0] = map[i - 1][0];
    }
    //공기청정기 아래쪽
    last_1 = 0; last_2 = 0;
    n = air_ref.second.first;
    m = air_ref.second.second;
    //오른쪽 이동
    for (int i = c-1; i >= 1; i--) {
        if (i == c-1)last_1 = map[n][c - 1];
        if (map[n][i - 1] == -1) map[n][i] = 0;
        else if (map[n][i] == -1) continue;
        else map[n][i] = map[n][i - 1];
    }
    //위쪽 이동
    for (int i = r-1; i > n; i--) {
        if (i == r - 1)last_2 = map[r - 1][c - 1];
        if (i == n + 1) {
            if (map[i][c-1] != -1) map[i][c-1] = last_1;
            continue;
        }
        if (map[i - 1][c - 1] == -1) {
            if (map[i][c - 1] == -1) continue;
            map[i][c - 1] = 0;
        }
        else if (map[i][c - 1] == -1)continue;
        else map[i][c-1] = map[i - 1][c - 1];
    }
    //왼쪽 이동
    for (int i = 0; i < c - 1; i++) {
        if (i == 0)last_1 = map[r-1][0];
        if (i == c - 2) {
            if (map[r-1][i] != -1 && map[r-1][c - 1] != -1) map[r-1][i] = last_2;
            else if (map[r-1][c - 1] == -1)map[r-1][i] = 0;
            continue;
        }
        if (map[r-1][i + 1] == -1) map[0][i] = 0;
        else if (map[r-1][i] == -1) continue;
        else map[r-1][i] = map[r-1][i + 1];
    }
    //아래쪽 이동
    for (int i = n; i < r-1; i++) {
        if (i == r - 2) {
            if (map[i][0] != -1) map[i][0] = last_1;
            continue;
        }
        if (map[i + 1][0] == -1) {
            if (map[i][0] == -1) continue;
            map[i][0] = 0;
        }
        else if (map[i][0] == -1) continue;
        else map[i][0] = map[i + 1][0];
    }
}
 
int main() {
    scanf("%d %d %d", &r, &c, &t);
    int ref_cnt = 0;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            scanf("%d", &map[i][j]);
            if (map[i][j] == -1) {
                if (ref_cnt == 0) { air_ref.first.first = i; air_ref.first.second = j; ref_cnt++; }
                else { air_ref.second.first = i; air_ref.second.second = j; }
            }
        }
    }
    while (t--) {
        spread();
        circulate();
    }
    int ans = 0;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (map[i][j] > 0) ans += map[i][j];
        }
    }
    printf("%d\n", ans);
}

아 너무 어렵다 진짜