문제

in Blog_old on Boj, 삼성sw역량테스트기출, C++

링크

격자판에 먼지들이 놓여있고, 첫번째 열 어딘가에는 세로로 2칸을 차지하는 공기청정기가 놓여있다. 먼지는 주변으로 확산하고, 공기청정기는 격자칸을 밀어서 순환시키는 기능을 한다. T초 뒤에 남은 먼지의 총 양을 구하는 문제이다.

접근

문제를 읽은 그대로 구현하면 어렵지 않게 풀 수 있다. 먼지 확산하는 함수를 하나 구현하고, 위쪽 순환과 아래쪽 순환을 각각 함수로 구현하면 쉽다. 또한 C++로 풀 때에는 algorithm의 swap을 이용하면 공기청정기의 작동을 간결하게 구현할 수 있다. 가장 처음에 임시변수를 선언하고, 여기에 공기청정기 바로 옆칸의 먼지 양을 넣어놓는다. 다음 칸부터 시작해서, 공기청정기 순환 방향을 따라 겹치지 않게 한바퀴 돌면서 계속 swap해주면 된다.

주의할 점

구현하면서 공기청정기 순환의 네 귀퉁이에서 겹치지 않게 잘 작동하는지 주의깊게 살펴보자. 공기청정기는 -1로 표시되어있으므로 마지막에 출력할 때 총합에 2를 더해야할 수 있다.

Code

링크

#include <algorithm>
#include <iostream>

using namespace std;

int R, C, T;
int A[50][50];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int origins[2] = {0, 0};

void dust_diffusion() {
    int delta[50][50] = {0};
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (A[i][j] > 0) {
                for (int d = 0; d < 4; d++) {
                    int x = i + dx[d];
                    int y = j + dy[d];
                    if (0 <= x && x < R && 0 <= y && y < C && A[x][y] != -1) {
                        delta[i][j] -= A[i][j] / 5;
                        delta[x][y] += A[i][j] / 5;
                    }
                }
            }
        }
    }
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            A[i][j] += delta[i][j];
        }
    }
}

void upper_circulation() {
    int origin_x = origins[0];
    int temp = A[origin_x][1];
    // lower row
    for (int i = 2; i < C; i++) {
        swap(temp, A[origin_x][i]);
    }
    A[origin_x][1] = 0;  // fresh air comes out.
    // right col
    for (int i = origin_x - 1; i >= 0; i--) {
        swap(temp, A[i][C - 1]);
    }
    // upper row
    for (int i = C - 2; i >= 0; i--) {
        swap(temp, A[0][i]);
    }
    // right col
    for (int i = 1; i < origin_x; i++) {
        swap(temp, A[i][0]);
    }
    // last portion will be absorbed.
}

void lower_circulation() {
    int origin_x = origins[1];
    int temp = A[origin_x][1];
    // upper row
    for (int i = 2; i < C; i++) {
        swap(temp, A[origin_x][i]);
    }
    A[origin_x][1] = 0;  // fresh air comes out.
    // right col
    for (int i = origin_x + 1; i < R; i++) {
        swap(temp, A[i][C - 1]);
    }
    // lower row
    for (int i = C - 2; i >= 0; i--) {
        swap(temp, A[R - 1][i]);
    }
    // left col
    for (int i = R - 2; i > origin_x; i--) {
        swap(temp, A[i][0]);
    }
    // last portion will be absorbed.
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> R >> C >> T;
    int foo = 0;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> A[i][j];
            if (A[i][j] == -1) {
                origins[foo++] = i;
            }
        }
    }
    while (T--) {
        dust_diffusion();
        upper_circulation();
        lower_circulation();
    }
    int ans = 0;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            ans += A[i][j];
        }
    }
    cout << ans + 2;
    return 0;
}

여담

삼성 기출 문제들은 격자칸을 주고 구현하는 문제들이 특히 많은 것 같다. 이들 문제들은 DFS/BFS를 이용하여 인접한 칸을 탐색하는 패턴과, 다양한 규칙의 시뮬레이션을 꼼꼼하게 구현하는 것만 익숙해진다면 대부분 어렵지 않게 해결할 수 있을 것 같다.