[백준 17144] 미세먼지 안녕! (C#, C++) - soo:bak

문제 링크

17144번 - 미세먼지 안녕!

설명

격자에 미세먼지와 공기청정기가 있습니다. 매초 미세먼지가 확산되고, 공기청정기가 공기를 순환시킵니다. T초 후 남아있는 미세먼지의 총량을 구하는 문제입니다.

접근법

매초 두 가지 과정이 순서대로 일어납니다. 확산과 공기청정기 작동입니다.

확산은 모든 칸에서 동시에 일어납니다. 각 칸의 미세먼지가 상하좌우로 퍼지는데, 확산되는 양은 해당 칸의 미세먼지를 5로 나눈 값입니다. 공기청정기가 있거나 격자를 벗어나는 방향으로는 확산되지 않습니다. 동시에 일어나므로 원본 배열을 참조하면서 새 배열에 결과를 누적해야 합니다.

공기청정기는 위쪽과 아래쪽 두 칸을 차지합니다. 위쪽에서는 반시계 방향으로, 아래쪽에서는 시계 방향으로 공기가 순환합니다. 순환 경로의 먼지가 한 칸씩 밀리고, 공기청정기로 들어오는 먼지는 정화되어 사라집니다.

이 두 과정을 T번 반복한 후 격자에 남은 미세먼지 양을 모두 더해 출력합니다.

Code

C#

using System;

namespace Solution {
  class Program {
    static int R, C, T;
    static int[,] board = new int[51, 51];
    static (int r, int c)[] air = new (int, int)[2];
    static readonly int[] dr = { -1, 1, 0, 0 };
    static readonly int[] dc = { 0, 0, 1, -1 };

    static void Diffuse() {
      var next = new int[51, 51];
      next[air[0].r, air[0].c] = next[air[1].r, air[1].c] = -1;
      for (var r = 0; r < R; r++) {
        for (var c = 0; c < C; c++) {
          if (board[r, c] <= 0)
            continue;
          var spread = board[r, c] / 5;
          var cnt = 0;
          for (var d = 0; d < 4; d++) {
            var nr = r + dr[d];
            var nc = c + dc[d];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C)
              continue;
            if (board[nr, nc] == -1)
              continue;
            next[nr, nc] += spread;
            cnt++;
          }
          next[r, c] += board[r, c] - spread * cnt;
        }
      }
      board = next;
    }

    static void Purify() {
      var ur = air[0].r;
      for (var r = ur - 1; r > 0; r--)
        board[r, 0] = board[r - 1, 0];
      for (var c = 0; c < C - 1; c++)
        board[0, c] = board[0, c + 1];
      for (var r = 0; r < ur; r++)
        board[r, C - 1] = board[r + 1, C - 1];
      for (var c = C - 1; c > 1; c--)
        board[ur, c] = board[ur, c - 1];
      board[ur, 1] = 0;

      var lr = air[1].r;
      for (var r = lr + 1; r < R - 1; r++)
        board[r, 0] = board[r + 1, 0];
      for (var c = 0; c < C - 1; c++)
        board[R - 1, c] = board[R - 1, c + 1];
      for (var r = R - 1; r > lr; r--)
        board[r, C - 1] = board[r - 1, C - 1];
      for (var c = C - 1; c > 1; c--)
        board[lr, c] = board[lr, c - 1];
      board[lr, 1] = 0;
    }

    static void Main(string[] args) {
      var first = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
      R = first[0];
      C = first[1];
      T = first[2];

      var airIdx = 0;
      for (var r = 0; r < R; r++) {
        var line = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
        for (var c = 0; c < C; c++) {
          board[r, c] = line[c];
          if (board[r, c] == -1)
            air[airIdx++] = (r, c);
        }
      }

      for (var t = 0; t < T; t++) {
        Diffuse();
        Purify();
      }

      var sum = 0;
      for (var r = 0; r < R; r++) {
        for (var c = 0; c < C; c++) {
          if (board[r, c] > 0)
            sum += board[r, c];
        }
      }
      Console.WriteLine(sum);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

int R, C, T;
int board[51][51];
pii air[2];

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

void diffuse() {
  int next[51][51] = {};
  next[air[0].first][air[0].second] = next[air[1].first][air[1].second] = -1;
  for (int r = 0; r < R; r++) {
    for (int c = 0; c < C; c++) {
      if (board[r][c] <= 0)
        continue;
      int spread = board[r][c] / 5;
      int cnt = 0;
      for (int d = 0; d < 4; d++) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (nr < 0 || nr >= R || nc < 0 || nc >= C)
          continue;
        if (board[nr][nc] == -1)
          continue;
        next[nr][nc] += spread;
        cnt++;
      }
      next[r][c] += board[r][c] - spread * cnt;
    }
  }
  memcpy(board, next, sizeof(board));
}

void purify() {
  int top = air[0].first;
  int bot = air[1].first;

  for (int r = top - 1; r > 0; r--)
    board[r][0] = board[r - 1][0];
  for (int c = 0; c < C - 1; c++)
    board[0][c] = board[0][c + 1];
  for (int r = 0; r < top; r++)
    board[r][C - 1] = board[r + 1][C - 1];
  for (int c = C - 1; c > 1; c--)
    board[top][c] = board[top][c - 1];
  board[top][1] = 0;

  for (int r = bot + 1; r < R - 1; r++)
    board[r][0] = board[r + 1][0];
  for (int c = 0; c < C - 1; c++)
    board[R - 1][c] = board[R - 1][c + 1];
  for (int r = R - 1; r > bot; r--)
    board[r][C - 1] = board[r - 1][C - 1];
  for (int c = C - 1; c > 1; c--)
    board[bot][c] = board[bot][c - 1];
  board[bot][1] = 0;
}

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

  cin >> R >> C >> T;
  int ai = 0;
  for (int r = 0; r < R; r++) {
    for (int c = 0; c < C; c++) {
      cin >> board[r][c];
      if (board[r][c] == -1)
        air[ai++] = {r, c};
    }
  }

  for (int t = 0; t < T; t++) {
    diffuse();
    purify();
  }

  int sum = 0;
  for (int r = 0; r < R; r++) {
    for (int c = 0; c < C; c++) {
      if (board[r][c] > 0)
        sum += board[r][c];
    }
  }

  cout << sum << "\n";

  return 0;
}