17144

1.문제

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

17144번: 미세먼지 안녕!

2.아이디어

1. 먼지 퍼뜨리기 (spread함수)

모든 먼지는 같은 시간에 동시에 일어나야함
but 우리는 한 좌표씩 먼지를 퍼뜨리므로 동시 처리가 안됨 (스레드 구현할순 없으니..)

가령 10 8 10 의경우

동시에 퍼뜨리면 9 10 9 이 되어야 하는데 만약 현재 구현한대로 왼쪽 -> 오른쪽 으로 한개씩 퍼뜨리게되면
10 8 10 -> 8 10 10 -> 10 6 12 -> 10 8 10  이나옴
즉 원래 가지고 있던 먼지만큼만 퍼뜨려야하는데 주위에서 받은 먼지의 총합을 퍼뜨리므로 계산 값이 달라짐 

그래서 배열을 두개를 선언해서 원본 배열은 건드리지않고 (자신의 고유한 먼지 값은 유지하려고) 먼지를 퍼뜨림

 

2. 먼지 옮기기 (runMachine함수)

현재 공기 청정기 윗부분의 dfs는 오 -> 위 -> 왼 -> 아래 순으로 들어감
즉 오른쪽으로 갈수 있는 상황이면 오른쪽으로 먼저 가게 되는데 

가령 반시계로 순회를 하여 1의 위치에 오게된경우 오른쪽을 먼저 이동해서 탐색하므로 아래쪽이아닌 오른쪽으로 가게되고 이는 잘못된 방향임
따라서 방향을 바꿔야 되는 시점이 오게되면(각 모서리) 방향을 바꿔주고 그게 아니라면 현재 진행하던 방향으로 계속 가게 해야됨
이를 구현하기 위해 파라미터 moveIdx로 진행방향을 넘겨줌

3.풀이

#include <bits/stdc++.h>

using namespace std;

int gx, gy;

int arr[51][51]; // 원본 배열
int arr2[51][51]; // 먼지 확산을 계산하기위해 0으로 초기화된 배열. 단, 공기청정기 위치는 표시해둬야함

int visited[51][51];

// 미세먼지 이동 방향
int x_move[] = { 0,0,-1,1 };
int y_move[] = { -1,1, 0, 0 };

// 공기청정기 윗부분 방향
int m_x_move[] = { 1,0,-1,0 };
int m_y_move[] = { 0,-1,0,1 };

// 공기청정기 아랫부분 방향
int m_x_move2[] = { 1,0,-1,0 };
int m_y_move2[] = { 0,1,0,-1 };


void spread(int y, int x) { // 먼지를 퍼뜨림

    // 모든 먼지는 같은 시간에 동시에 일어나야함
    // but 우리는 한 좌표씩 먼지를 퍼뜨리므로 동시 처리가 안됨 (스레드 구현할순 없으니..)
    // 
    // 9  10 9
    // 10 8 10 의경우 동시에 퍼뜨리면 9 10 9 이 되어야 하는데 만약 현재 구현한대로 왼쪽 -> 오른쪽 으로 한개씩 퍼뜨리게되면
    // 10 8 10 -> 8 10 10 -> 10 6 12 -> 10 8 10  이나옴
    // 즉 원래 가지고 있던 먼지만큼만 퍼뜨려야하는데 주위에서 받은 먼지의 총합을 퍼뜨리므로 계산 값이 달라짐 
    // 
    // 그래서 배열을 두개를 선언해서 원본 배열은 건드리지않고 (자신의 고유한 먼지 값은 유지하려고) 먼지를 퍼뜨림

    int curr = arr[y][x]; // 1. x y 좌표에 해당하는 고유한 먼지값을 가져옴
    int cnt = 0;

    for (int i = 0; i < 4; i++) {
        int nx = x + x_move[i];
        int ny = y + y_move[i];

        if (nx < 0 || nx >= gx || ny < 0 || ny >= gy || visited[ny][nx] || arr[ny][nx] == -1)
            continue;

        arr2[ny][nx] += curr / 5; // arr2에 x,y 로부터 퍼뜨린 먼지 값들을 넣어줌

        cnt++;
    }

    // 먼지를 퍼뜨린 후 x,y에 남아있는 먼지값을 더해줌
    arr2[y][x] += arr[y][x] - (curr / 5) * cnt;

    // 즉, x,y에서 먼지를 퍼트리고 남은 먼지 + 주위로 부터 받은 먼지 -> 원하는 결과값

}

void runMachine(int y, int x, int prev, int dir, int moveIdx) { // 공기청정기로 인한 먼지 이동
    visited[y][x] = 1;

    int curr = arr2[y][x];

    if (curr < 0)
        curr = 0;

    arr2[y][x] = prev; // 값을 한칸씩 옮겨야 하므로 이전 좌표의 값을 파라미터로 넘겨서 현재 위치로 넘김

    for (int i = 0; i < 4; i++) {
        int ny, nx;
        if (dir == 0) { // 공기청정기 윗부분
            nx = x + m_x_move[moveIdx];
            ny = y + m_y_move[moveIdx];

            // 현재 공기 청정기 윗부분의 dfs는 오 -> 위 -> 왼 -> 아래 순으로 들어감
            // 즉 오른쪽으로 갈수 있는 상황이면 오른쪽으로 먼저 가게 되는데 
            // 0 0 0
            // 1 0 0
            // 0 0 0
            // 가령 반시계로 순회를 하여 1의 위치에 오게된경우 오른쪽을 먼저 이동해서 탐색하므로 아래쪽이아닌 오른쪽으로 가게되고 이는 잘못된 방향임
            // 따라서 방향을 바꿔야 되는 시점이 오게되면(각 모서리) 방향을 바꿔주고 그게 아니라면 현재 진행하던 방향으로 계속 가게 해야됨
            // 파라미터 moveIdx로 진행방향을 넘겨줌

            if (nx < 0 || nx >= gx || ny < 0 || ny >= gy) { 
                nx = x + m_x_move[(moveIdx + 1) % 4];
                ny = y + m_y_move[(moveIdx + 1) % 4];
                moveIdx = (moveIdx + 1) % 4;
            }
        }
        else { // 공기청정기 아랫부분
            nx = x + m_x_move2[moveIdx];
            ny = y + m_y_move2[moveIdx];

            if (nx < 0 || nx >= gx || ny < 0 || ny >= gy) {
                nx = x + m_x_move2[(moveIdx + 1) % 4];
                ny = y + m_y_move2[(moveIdx + 1) % 4];
                moveIdx = (moveIdx + 1) % 4;
            }
        }
     
        if (arr2[ny][nx] == -1)
            return;

        if (visited[ny][nx])
            continue;
        
        runMachine(ny, nx, curr, dir, moveIdx);
    }
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;

    cin >> gy >> gx >> t;

    for (int i = 0; i < gy; i++) {
        for (int j = 0; j < gx; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == -1)
                arr2[i][j] = -1; // 공기 청정기의 위치 arr2에 기록
        }
    }

    while (t--) {

        memset(visited, 0, sizeof(visited)); // 다회차를 위해 방문배열 초기화

        // 1. 먼지 확산
        for (int i = 0; i < gy; i++) {
            for (int j = 0; j < gx; j++) {
                if (arr[i][j] != -1 && arr[i][j] != 0) // 현재 좌표가 공기청정기이거나 먼지값이 0 이면 퍼뜨리지 않음
                    spread(i, j);
            }
        }

        // 2. 공기청정기 가동

        // 2.1 공기 청정기 위치 찾기
        int posY = 0; 
        
        // 공기청정기의 윗부분 y 위치 찾기 -> x는 항상 1열(0)이므로
        for (int i = 0; i < gy; i++) { 
            if (arr[i][0] == -1) {
                posY = i;
                break;
            }
        }

        // 2.2 공기청정기 위 가동
        runMachine(posY, 0, -1, 0, 0);

        // 2.3 공기청정기 아래 가동
        runMachine(posY + 1, 0, -1, 1, 0);

        // 다회차를 위해 결과값이 들어있는 arr2배열을 arr 배열로 복사.
        copy(&arr2[0][0], &arr2[0][0] + 51 * 51, &arr[0][0]);

        // arr2 다시 써야하므로 초기화
        memset(arr2, 0, sizeof(arr2));

        arr2[posY][0] = -1;
        arr2[posY + 1][0] = -1;
    }

    // 3. 미세먼지 합계
    int sum = 0;
    for (int i = 0; i < gy; i++) {
        for (int j = 0; j < gx; j++) {
            sum += arr[i][j];
        }
    }

    cout << sum + 2 << "\n"; // 공기청정기 -1 이 두개 있으므로 +2

    return 0;
}