[Unsolved][C++] 백준 17144 미세먼지 안녕!

www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

 

1. 서론

 

아... 결국 골드의 벽을 넘지 못하고 답을 봐버렸으나... 내가 고민했던 포인트에서의 답이 명확하게 제시되어 있는 풀이를 발견했다.

그래서 그분의 코드를 보며 문제를 어떻게 풀었는지 이해했는데 그 풀이를 까먹기 전에 적어두려 한다.

 

2. 문제 풀이

 

문제가 길고 조건이 많다보니 정신 놓기가 쉬운 문제다. 꼭 문제의 여러 가지 조건 사항들을 유심히 봐야 한다.

미세먼지를 제거하기 위해서 공기청정기를 돌린다. 이때 공기청정기는 RxC 범위 안에서 돈다. 

미세먼지의 값은 숫자로 주어지고, 미세먼지가 없는 칸에는 0이 공기청정기가 위치하고 있는 칸에는 -1이 주어진다.

1초 동안 미세먼지가 확산되고, 공기청정기가 작동한다.

 

 

-미세먼지가 확산되는 경우 고려해야 할 것

미세먼지는 미세먼지가 있는 칸을 기준으로 인접한 네 방향으로 확산된다.(동, 서, 남, 북)

그리고 미세먼지가 있는 모든 칸에서 동시에 일어난다.

인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다. 

동서남북으로 확산되는 양은 X / 5 이며 소수점은 버린다.

X위치에 남은 미세먼지 양은 X - (X / 5) * 확산된 방향의 개수이다. 확산된 방향은 4일 수도 그보다 작을 수도 있다.(칸이 없거나 공기청정기가 있는 경우는 그 방향으로 확산되지 않기 때문에)

 

 

-공기청정기가 작동하는 경우 고려해야 할 것

공기청정기의 윗부분은 반시계방향으로 순환하고, 아랫부분은 시계방향으로 순환한다.

바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.

*공기청정기는 항상 1번열에 설치되어 있다.

*공기청정기로 들어간 미세먼지는 모두 정화된다.

=> 공기청정기로 빨려들어간 미세먼지 값은 소실되어도 상관없다. (내가 고민했던 포인트)

 

-나의 생각

 

나는 일단 공기청정기가 항상 1번열에 있다는 사실을 풀이를 보기 전까지 몰랐다. (문제를 대충 읽었기 때문에)

그래서 공기청정기의 좌표값을 따로 x1, y1, x2, y2로 따로 적어놨었다... (바보 같음)

그리고 배열을 두 개 쓸까, 하나 쓸까 고민하다 결국 하나만 써서 더 어려운 길로 가게 되었다.

하나만 써야겠다고 생각한 이유는 바람이 불면서 미세먼지가 옆칸으로 밀리는 경우 값이 유실될까 봐...

배열의 수는 뭐 어쨌든 이래도 저래도 상관없는 문제였다.

그러고 나서 나는 엄청나게 막일로 미세먼지를 확산시켰는데 결과적으로 값이 틀린건 아니지만 너무 길고 코드가 반복되어 자리만 차지하는 느낌이었다. (내가 봤던 풀이에서는 i,j 값을 때에따라 조절해서 코드를 간결하고 반복이 일어나지 않게 짰는데 나도 이런 방법이 있을 거라고 생각은 했지만 차마 내 머리로 그 풀이를 떠올리지 못해 노가다를 택했다.)

이렇게 확산하는 코드를 돌리며 확산된 방향의 개수를 count 했다. 

여기까지는 나도 노가다로 어떻게든 짰다. 그런데... 공기청정기가 도는 부분에서 나는 꽉 막히면서 머리가 멈추고 말았다.

 

 

 

공기청정기가 작동하는 과정

 

 

공기청정기는 이런 패턴으로 작용한다. 그래서 나는 단순하게 저 방향을 따라서 숫자들을 밀어야 한다고 생각했다.

윗부분을 예시로 들자면 3번째 줄에서 왼 -> 오 방향으로 먼저 밀고 그 끝부분까지 밀고 나면 밑에서 위로 또 밀고....

이런 식으로 구현해야 한다고 생각했다. (문제에 그렇게 나와 있으니까)

그런데 이런 순서대로 숫자들을 밀고 나면 문제가 생긴다. 바로 숫자들이 밀리면서 값이 유실될 수 있다는 점이다. 그래서 난 그 밀린 마지막항 한 개의 숫자를 변수에 저장해놨다가 다른 방향으로 값을 넣어줘야겠다고 생각했는데 그게 보통 복잡한 문제가 아니었다.

마지막항을 저장하고 밀고, 다음 방향으로 밀기 전에 값을 넣어주면 또 그 첫 번째 항의 값이 유실되니까 밀고 나서 넣어준다고 생각하면 또 다른 변수에 밀려서 유실될 값을 또 저장해줘야 하는 문제가 생겼다. 이걸 다 저장해주고 나중에 넣어주는 게 말이 안 된다고 생각해 내가 생각을 잘못했구나 싶어서 코드 짜는 걸 멈췄다. (너무 복잡해지고 코드가 더러워지기 때문)

그렇게 고민하다가 결국 답을 봤다.

 

3. 코드 설명

 

출처: hddcp.tistory.com/21

[백준] 17144 - 미세먼지 안녕!

 

이 블로그에 있는 코드를 봤다.

 

#include <cstdio>
 
int main(){
    int r, c, t;
    int room[51][51];
    int cl;
    int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
    //동서남북 사방으로 확산하기 위해 만든 배열
    
    scanf("%d %d %d", &r, &c, &t);
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            scanf("%d", &room[i][j]);
            if(room[i][j] == -1){
                cl = i;
            }
        }
    }
    cl--; // 공기청정기의 위쪽을 가리킴
 
    for(int time=0; time<t; time++){
        // 확산
        // 이동되는 먼지 양 계산
        int exp[51][51] = {};
        for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                if(room[i][j] != 0 && room[i][j] != -1){
                    int cnt = 0;
                    for(int k=0; k<4; k++){
                        int ay = i + dy[k], ax = j + dx[k];
                        if(ay >= 0 && ay < r && ax >= 0 && ax < c && room[ay][ax] != -1){
                            cnt++;
                            exp[ay][ax] += room[i][j] / 5;
                        }
                    }
                    room[i][j] -= (room[i][j] / 5) * cnt;
                }
            }
        }
        // 먼지 이동 적용
        for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                room[i][j] += exp[i][j];
            }
        }
 
        // 순환
        // 삭제되는 부분부터 제거해야 다른 항이 소실되지 않음
 
        // 윗방향 순환
        // 위에서 아래 방향으로
        for(int i=cl-1; i>=1; i--){
            room[i][0] = room[i-1][0];
        }
        // 우측에서 좌측으로
        for(int i=0; i<c-1; i++){
            room[0][i] = room[0][i+1];
        }
        // 아래에서 위
        for(int i=0; i<cl; i++){
            room[i][c-1] = room[i+1][c-1];
        }
        // 좌에서 우
        for(int i=c-1; i>=1; i--){
            room[cl][i] = room[cl][i-1];
        }
        // 정화 공기로 채워진 장소
        room[cl][1] = 0;
 
 
        // 아래방향 순환
        // 아래에서 위 방향으로
        for(int i=cl+2; i<r-1; i++){
            room[i][0] = room[i+1][0];
        }
        // 좌측에서 우측으로
        for(int i=0; i<c-1; i++){
            room[r-1][i] = room[r-1][i+1];
        }
        // 위에서 아래
        for(int i=r-1; i>cl+1; i--){
            room[i][c-1] = room[i-1][c-1];
        }
        // 좌에서 우
        for(int i=c-1; i>=1; i--){
            room[cl+1][i] = room[cl+1][i-1];
        }
        // 정화 공기로 채워진 장소
        room[cl+1][1] = 0;
    }
 
    int sum = 2; // 공기 청정기 2 (-1 + -1)
    for(int i=0; i<r; i++){
        for(int j=0; j<c; j++){
            sum += room[i][j];
        }
    }
    printf("%d", sum);
 
    return 0;
}

 

이 코드에서 내가 고민했던 포인트의 해법을 명확하게 제시해주고 있다.

소실될까 봐 값을 저장하고 어쩌고 할 것이 없었다. 내가 놓쳤던 것은 미세먼지가 공기청정기로 들어가면 그 값이 유실되어도 된다는 점이다.

이 말은 즉, 미세먼지에서 바람이 나가는 방향 먼저 밀어주는 게 아니라 미세먼지가 빨아들여지는 부분을 먼저 밀면 그런 점을 신경 쓰지 않아도 된다는 것이다. 왜냐면 맨 앞의 값이 유실되고(공기청정기가 빨아들여) 그 값을 미리 밀어주다 보면 코너 부분에서 값을 잃을까 봐 고민할 필요가 사라지기 때문이다. (이미 밀릴 값이 비어져있어서) 결국엔 내가 생각했던 순서와 반대로 밀면 이 고민이 쉽게 해결된다는 것이다. 그리고 끝까지 코드를 다 안 짜서 몰랐는데 공기청정기 값이 -1 + -1 = -2니까 미리 그 값을 더한 것도 내가 놓친 포인트다. 

 

이외에도 동서남북으로 미세먼지가 확산되는 것 또한 배열을 이용해서 값이 계속 바뀌어서 적용되게 풀었는데 내가 생각지도 못한... 그 풀이다. 배열 두 개에 미리 좌표값을 저장하고 반복문을 돌리는 것이다. 반복문은 순서대로 0,1 | 1,0 | 0,-1 | -1, 0 즉, 동서남북 방향을 다 볼 수 있게 설정되어 있다. 그리고 미세먼지가 있는 모든 칸에서 동시에 미세먼지 확산이 이루어지기 때문에 미세먼지의 값이 중간에 변하면 안 되므로 빈 배열을 하나 더 붙여서 그 변하는 값을 따로 저장한 후, 모든 칸에서 확산이 완료된 후 값을 원래의 배열에 더해야 한다.

 

코드 자체는 간결한데 생각해야 할 조건이 조금 있다... 구현도 좀 내 기준 복잡하다. (신경 써야 하는 포인트들이 있어서,,, 나는 방향감각이 없어서 동서남북이나... 코드를 미는 게 어렵다)

이해하고 나니 참 쉬운 문제인데 (어렵긴 한데 복잡한 알고리즘 구현은 아니라서) 안 풀리고 여기까지 생각을 못하니까 답답하다^^

 

나중에... 다시 푸는 날 오길 빌며 Unsolved 폴더에 넣어준다...