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

풀이 시간: 2h30m35s08(초기 코드) + 48m12s57

시간 복잡도: O(RCT)

공간 복잡도: O(RC)

참고 자료: https://yabmoons.tistory.com/238

문제

입력

첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다.

둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.

출력

첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

문제 풀이

초기 코드

#include <iostream>
using namespace std;
int R, C, T, t = 0, sum = 0;
int arr[50][50] = { 0, };
int air1 = -1, air2 = -1; // 공기 청정기는 항상 1열이므로 행의 값만 입력 받음
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 4방향

void clean(int num) {
    int cX, cY = 1; // 현재 위치, 초깃값: 공기청정기의 오른쪽 위치
    if (num == 1) cX = air1;
    else cX = air2;
    int nX = 0, nY = 0; // 다음 위치
    int curD = 0, cValue = 0, nValue = 0; // 현재 방향, 현재 위치 값, 다음 위치 값
    // 공기청정기 air1/air2 작동
    while(arr[cX][cY] != -1) {
        // 범위 벗어날 경우 방향 갱신
        if (cX + dir[curD][0] < 0 || cX + dir[curD][0] >= R 
        || cY + dir[curD][1] < 0 || cY + dir[curD][1] >= C) {
            if (num == 1) curD = (curD + 3) % 4; // 반시계
            else curD = (curD + 1) % 4; // 시계
        }
        // 다음 위치와 값 갱신
        nX = cX + dir[curD][0];
        nY = cY + dir[curD][1];
        nValue = arr[nX][nY];
        // 미세먼지 값 이동
        if (nX >= 0 && nX < R && nY >= 0 && nY < C) {
            // 공기청정기 위치가 아닌 경우에만 값 이동
            if (arr[nX][nY] != -1) arr[nX][nY] = cValue;
            // 현재 위치와 값 갱신
            cX = nX;
            cY = nY;
            cValue = nValue;
        }
    }
}

void diff() {
    while (t < T) {
        int tempArr[50][50] = { 0, };
        // 미세먼지 확산
        for (int i = 0; i < R; ++i) {
            for (int j = 0; j < C; ++j) {
                if (arr[i][j] <= 0) continue; // 공기청정기와 미세먼지 없는 곳 제외
                int cnt = 0; // 현재 위치로부터 확산된 개수
                for (int k = 0; k < 4; ++k) { // 4방향 탐색
                    int nX = i + dir[k][0];
                    int nY = j + dir[k][1];
                    if (nX < 0 || nX >= R || nY < 0 || nY >= C || arr[nX][nY] == -1) continue;
                    tempArr[nX][nY] += arr[i][j] / 5; // 확산되는 양 계산하여 더함
                    cnt++;
                }
                arr[i][j] -= (arr[i][j] / 5) * cnt; // 미세먼지 남은 양 계산
            }
        }
        for (int i = 0; i < R; ++i) {
            for (int j = 0; j < C; ++j) {
                if (arr[i][j] == -1) continue; // 공기청정기 제외
                arr[i][j] += tempArr[i][j];
            }
        }
        clean(1); // air1 공기청정기
        clean(2); // air2 공기청정기
        t++; // 시간 추가
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> R >> C >> T;
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            cin >> arr[i][j];
            if (arr[i][j] == -1) { // 공기청정기 위치 저장
                if (air1 == -1) air1 = i;
                else air2 = i;
            }
        }
    }
    diff();
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            if (arr[i][j] == 0 || arr[i][j] == -1) continue;
            sum += arr[i][j];
        }
    }
    cout << sum;
    return 0;
}

 

위 코드는 마지막 예제 3개(6, 7, 8)가 답이 다르게 나왔다.

확인해보니 공기청정기 작동하는 clean() 함수 내부에서 한 칸씩 이동해주는 과정에 문제가 발생하는 것 같았다.

 

다음 블로그를 참고하여 공기청정기가 작동하는 방식을 다르게 수정해보았다.

 

우선 함수를 호출하는 전체 틀을 수정하였다.

for (int i = 0; i < T; ++i) { diff(); clean(); }

원래는 diff() 함수 내부에 while 문과 clean() 함수가 호출되어 있었는데, while문을 for문으로 바꾸어 main() 함수로 빼내었고, clean() 함수도 같이 빼주었다.

이렇게 리팩토링함으로써 각 함수의 역할을 더 명확히 분리할 수 있다.

for (int i = 0; i < R; ++i)
    for (int j = 0; j < C; ++j)
        arr[i][j] += tempArr[i][j];

위 부분도 수정해주었는데, 실질적으로 공기청정기 부분은 어차피 tempArr[i][j]가 0이기 때문에 if문을 굳이 쓰지 않아도 tempArr을 더해줌으로써 해당 공기청정기 부분의 값이 변동될 경우는 없다. 따라서 if문을 삭제하여 시간을 단축하였다.

for (int i = 0; i < R; ++i) {
    for (int j = 0; j < C; ++j) {
        if (arr[i][j] <= 0) continue; // 공기청정기와 미세먼지 없는 곳 제외
        for (int k = 0; k < 4; ++k) { // 4방향 탐색
            int nX = i + dir[k][0];
            int nY = j + dir[k][1];
            if (nX < 0 || nX >= R || nY < 0 || nY >= C || arr[nX][nY] == -1) continue;
            tempArr[nX][nY] += arr[i][j] / 5; // 확산되는 양 계산하여 더함
            arr[i][j] -= arr[i][j] / 5; // 미세먼지 남은 양 계산 -> 코드 수정 부분
        }
    }
}

위 부분에서는 cnt 값을 없애고 그냥 직접 빼주는 방식으로 변경하였다. 이렇게 하면 좀 더 코드를 간결하게 작성할 수 있다.

if (arr[i][j] > 0) { // 공기청정기와 미세먼지 없는 곳 제외
    for (int k = 0; k < 4; ++k) { // 4방향 탐색
        int nX = i + dir[k][0];
        int nY = j + dir[k][1];
        if (nX >= 0 && nX < R && nY >= 0 && nY < C && arr[nX][nY] != -1) {
            tempArr[nX][nY] += arr[i][j] / 5; // 확산되는 양 계산하여 더함
            arr[i][j] -= arr[i][j] / 5; // 미세먼지 남은 양 계산
        }
    }
}

for (int i = 0; i < R; ++i)
    for (int j = 0; j < C; ++j)
        if (arr[i][j] > 0)
        	sum += arr[i][j];

그리고 위 두 개의 코드와 같이 if문도 전부 반대로 구현하여 좀 더 가독성있게 코드를 수정해보았다.

---

다음은 결과에 직접 영향을 준 코드 수정 부분이다.

int spreadAmount = arr[i][j] / 5;
for (int k = 0; k < 4; ++k) { // 4방향 탐색
    int nX = i + dir[k][0];
    int nY = j + dir[k][1];
    if (nX >= 0 && nX < R && nY >= 0 && nY < C && arr[nX][nY] != -1) {
        tempArr[nX][nY] += spreadAmount; // 확산되는 양 계산하여 더함
        arr[i][j] -= spreadAmount; // 미세먼지 남은 양 계산
    }
}

여기 확산되는 부분 코드를 변경했는데, spreadAmount 값을 따로 빼주어 더해주었다.

아래처럼 하면 답이 이상하게 나오고 위에 처럼 하면 정답코드가 되는데 그 이유를 사실 아직도 잘 모르겠다...

for (int k = 0; k < 4; ++k) { // 4방향 탐색
    int nX = i + dir[k][0];
    int nY = j + dir[k][1];
    if (nX >= 0 && nX < R && nY >= 0 && nY < C && arr[nX][nY] != -1) {
        tempArr[nX][nY] += arr[i][j] / 5; // 확산되는 양 계산하여 더함
        arr[i][j] -= arr[i][j] / 5; // 미세먼지 남은 양 계산
    }
}

 

 

그 다음 제일 중요한 공기청정기 작동하는 clean() 함수를 전부 수정해주었다.

기존에는 dir 변수를 사용해 방향을 바꿔주면서 현재 값을 저장해두고 다음 값을 갱신하는 방식으로 진행했다면 이번에는 아예 for 문을 여러 번 돌려서 각각의 방향대로 전부 이동시켰다.

void clean() {
    // 위쪽 공기 청정기 작동 (air1)
    for (int i = air1 - 1; i > 0; --i) // 공기 청정기 세로 라인
        arr[i][0] = arr[i - 1][0];
    for (int j = 0; j < C - 1; ++j) // 맨 상단 라인
        arr[0][j] = arr[0][j + 1];
    for (int i = 0; i < air1; ++i) // 맨 오른쪽 세로 라인
        arr[i][C - 1] = arr[i + 1][C - 1];
    for (int j = C - 1; j > 1; --j) // 공기 청정기 가로 라인
        arr[air1][j] = arr[air1][j - 1];
    arr[air1][1] = 0; // 처음 시작 위치(공기 청정기의 우측)는 0

    // 아래쪽 공기 청정기 작동 (air2)
    for (int i = air2 + 1; i < R - 1; ++i) // 공기 청정기 세로 라인
        arr[i][0] = arr[i + 1][0];
    for (int j = 0; j < C - 1; ++j) // 맨 하단 라인
        arr[R - 1][j] = arr[R - 1][j + 1];
    for (int i = R - 1; i > air2; --i) // 맨 오른쪽 세로 라인
        arr[i][C - 1] = arr[i - 1][C - 1];
    for (int j = C - 1; j > 1; --j) // 공기 청정기 가로 라인
        arr[air2][j] = arr[air2][j - 1];
    arr[air2][1] = 0; // 처음 시작 위치(공기 청정기의 우측)는 0
}

전체 코드

#include <iostream>
using namespace std;
int R, C, T, sum = 0;
int arr[50][50] = { 0, };
int air1 = -1, air2 = -1; // 공기 청정기는 항상 1열이므로 행의 값만 입력 받음
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 4방향

void clean() {
    // 위쪽 공기 청정기 작동 (air1)
    for (int i = air1 - 1; i > 0; --i) // 공기 청정기 세로 라인
        arr[i][0] = arr[i - 1][0];
    for (int j = 0; j < C - 1; ++j) // 맨 상단 라인
        arr[0][j] = arr[0][j + 1];
    for (int i = 0; i < air1; ++i) // 맨 오른쪽 세로 라인
        arr[i][C - 1] = arr[i + 1][C - 1];
    for (int j = C - 1; j > 1; --j) // 공기 청정기 가로 라인
        arr[air1][j] = arr[air1][j - 1];
    arr[air1][1] = 0; // 처음 시작 위치(공기 청정기의 우측)는 0

    // 아래쪽 공기 청정기 작동 (air2)
    for (int i = air2 + 1; i < R - 1; ++i) // 공기 청정기 세로 라인
        arr[i][0] = arr[i + 1][0];
    for (int j = 0; j < C - 1; ++j) // 맨 하단 라인
        arr[R - 1][j] = arr[R - 1][j + 1];
    for (int i = R - 1; i > air2; --i) // 맨 오른쪽 세로 라인
        arr[i][C - 1] = arr[i - 1][C - 1];
    for (int j = C - 1; j > 1; --j) // 공기 청정기 가로 라인
        arr[air2][j] = arr[air2][j - 1];
    arr[air2][1] = 0; // 처음 시작 위치(공기 청정기의 우측)는 0
}

void diff() {
    int tempArr[50][50] = { 0, };
    // 미세먼지 확산
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            if (arr[i][j] > 0) { // 공기청정기와 미세먼지 없는 곳 제외
                int spreadAmount = arr[i][j] / 5;
                for (int k = 0; k < 4; ++k) { // 4방향 탐색
                    int nX = i + dir[k][0];
                    int nY = j + dir[k][1];
                    if (nX >= 0 && nX < R && nY >= 0 && nY < C && arr[nX][nY] != -1) {
                        tempArr[nX][nY] += spreadAmount; // 확산되는 양 계산하여 더함
                        arr[i][j] -= spreadAmount; // 미세먼지 남은 양 계산
                    }
                }
            }
        }
    }
    for (int i = 0; i < R; ++i)
        for (int j = 0; j < C; ++j)
            arr[i][j] += tempArr[i][j];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(0);
    cin >> R >> C >> T;
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            cin >> arr[i][j];
            if (arr[i][j] == -1) { // 공기청정기 위치 저장
                if (air1 == -1) air1 = i;
                else air2 = i;
            }
        }
    }
    
    for (int i = 0; i < T; ++i) { diff(); clean(); }

    for (int i = 0; i < R; ++i)
        for (int j = 0; j < C; ++j)
            if (arr[i][j] > 0) sum += arr[i][j];
    cout << sum;
    return 0;
}

 

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

17144번: 미세먼지 안녕!