17144-미세먼지 안녕!

www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

본문에 앞서 해당 문제는 다른 분들의 솔루션을 참고하고 풀었음을 밝힙니다.

 

본 문제는 시뮬레이션 문제입니다. 알고리즘은 문제의 규칙에 맞게 아래의 순으로 진행됩니다.

 

1. 미세먼지 확산

*미세먼지는 확산시, 미세먼지가 존재하는 칸에도 누적되는 방식으로 확산이 됩니다.

 

2. 미세먼지 이동

 

3. 위 과정(1. ~ 2.) T번 반복

 

 

문제를 풀다가 미세먼지를 시계/반시계 방향으로 이동시키는 부분을 깔끔하게 구현하는 방법을 떠올리지 못하여 결국 아래의 솔루션을 참고하여 문제를 풀었습니다.

 

mygumi.tistory.com/351

백준 17144번 미세먼지 안녕! :: 마이구미

아래의 함수는 공기 청정기의 동작 과정을 구현한 함수 입니다.

 

cw_dr, cw_dc는 시계 방향(Clockwise)으로 미세 먼지를 이동시키기 위해 사용되는 변수입니다.

ccw_dr, ccw_dc는 반시계 방향(Counter Clockwise)으로 미세 먼지를 이동시키기 위해 사용되는 변수입니다.

 

해당 함수는 공기 청정기의 상단부 혹은 하단부의 위치와 청소 모드(시계 방향, 반시계 방향)을 파라미터로써 입력 받습니다.

 

미세 먼지를 이동시키는 방법을 구현함에 있어 먼저 미세 먼지를 이동시키기 이전에 방의 상태를 복사해줍니다. 복사를 해주는 이유는 먼지를 옆으로 한 칸 옮기게 되면 해당칸에 원래있던 먼지의 값을 잃게되기 때문입니다. 그런다음, 공기 청정기 바로 우측에 있는 칸을 0으로 채웁니다. 이후, 시계/반시계 방향으로 움직여가며 먼지를 방향에 맞게 옮깁니다. 코드를 보시면 어느 한 방향으로 일정하게 움직이다가 방을 벗어나는 경우, 방향을 전환하는 것을 확인하실 수 있습니다. 최종적으로 공기 청정기의 위치까지 오게됩니다.

 

 

enum{CW, CCW};

int cw_dr[4] = {0, 1, 0, -1};
int cw_dc[4] = {1, 0, -1, 0};

int ccw_dr[4] = {0, -1, 0, 1};
int ccw_dc[4] = {1, 0, -1, 0};

void clean(int r, int c, int mode)
// r: 공기청정기 상단부 혹은 하단부의 행 위치
// c: 공기청정기 상단부 혹은 하단부의 열 위치
{
    int copy_map[51][51];
    std::copy(&map[0][0], &map[0][0]+51*51, &copy_map[0][0]);

    int* dr = (mode==CW)?cw_dr:ccw_dr;
    int* dc = (mode==CW)?cw_dc:ccw_dc;

    int nr = r;
    int nc = c+1;

    map[nr][nc] = 0;

    for(int dir = 0; dir < 4; dir++)
    {
        while(true)
        {
            if(nr + dr[dir] < 1 || nr + dr[dir] > R) break;
            if(nc + dc[dir] < 1 || nc + dc[dir] > C) break;

            if(nr + dr[dir] == r and nc + dc[dir] == c) break;

            map[nr + dr[dir]][nc + dc[dir]] = copy_map[nr][nc];

            nr += dr[dir];
            nc += dc[dir];
        }
    }
}

 

시계/반시계 방향으로 배열을 순회하는 코드를 참고하였을때, 놀라움을 금치 못하였습니다. 정말 아름다운 코드라고 생각하였습니다.

 

 

코드

#include <iostream>
#include <queue>

using namespace std;

int R; //행
int C; //열
int T; //시간

int map[51][51];

struct Robot
{
    int r;
    int c;
    Robot(int r, int c)
    {
        this->r = r;
        this->c = c;
    }
};

vector<Robot> robots;

struct Dust
{
    int r;
    int c;
    int d;
    Dust(int r, int c, int d)
    {
        this->r = r;
        this->c = c;
        this->d = d;
    }
};

queue<Dust> queue_dust;

int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};

enum{CW, CCW};

int cw_dr[4] = {0, 1, 0, -1};
int cw_dc[4] = {1, 0, -1, 0};

int ccw_dr[4] = {0, -1, 0, 1};
int ccw_dc[4] = {1, 0, -1, 0};

void clean(int r, int c, int mode)
// r: 공기청정기 상단부 혹은 하단부의 행 위치
// c: 공기청정기 상단부 혹은 하단부의 열 위치
{
    int copy_map[51][51];
    std::copy(&map[0][0], &map[0][0]+51*51, &copy_map[0][0]);

    int* dr = (mode==CW)?cw_dr:ccw_dr;
    int* dc = (mode==CW)?cw_dc:ccw_dc;

    int nr = r;
    int nc = c+1;

    map[nr][nc] = 0;

    for(int dir = 0; dir < 4; dir++)
    {
        while(true)
        {
            if(nr + dr[dir] < 1 || nr + dr[dir] > R) break;
            if(nc + dc[dir] < 1 || nc + dc[dir] > C) break;

            if(nr + dr[dir] == r and nc + dc[dir] == c) break;

            map[nr + dr[dir]][nc + dc[dir]] = copy_map[nr][nc];

            nr += dr[dir];
            nc += dc[dir];
        }
    }
}

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

    //freopen("17144.txt", "r", stdin);

    cin >> R >> C >> T;

    for(int r = 1; r <= R; r++)
        for(int c = 1; c <= C; c++)
        {
            cin >> map[r][c];
            if(map[r][c] > 0) queue_dust.push(Dust(r, c, map[r][c]));
            else if(map[r][c] == -1) robots.push_back(Robot(r, c));
        }

    Robot robot_upper = robots[0];
    Robot robot_lower = robots[1];

    for(int t = 1; t <= T; t++)
    {
        //먼지 확산
        if(queue_dust.empty())
        {
            for(int r = 1; r <= R; r++)
                for(int c = 1; c <= C; c++)
                    if(map[r][c] > 0) queue_dust.push(Dust(r, c, map[r][c]));
        }

        while(!queue_dust.empty())
        {
            Dust dust = queue_dust.front();
            queue_dust.pop();

            int r = dust.r;
            int c = dust.c;
            int d = dust.d;
            int spreaded_d = static_cast<int>(dust.d/5);

            for(int dir = 0; dir < 4; dir++)
            {
                int nr = r + dr[dir];
                int nc = c + dc[dir];

                if(nr < 1 || nc < 1 || nr > R || nc > C) continue;
                if(map[nr][nc] == -1) continue;

                map[nr][nc] += spreaded_d;
                map[r][c] -= spreaded_d;
            }
        }

        //공기청정기 작동
        clean(robot_upper.r, robot_upper.c, CCW);
        clean(robot_lower.r, robot_lower.c, CW);
    }

    int sum = 0;
    for(int r = 1; r <= R; r++)
        for(int c = 1; c <= C; c++)
            if(map[r][c] > 0) sum += map[r][c];
    cout << sum;

    return 0;
}