[백준 2563] 색종이 (C#, C++) - soo:bak

문제 링크

2563번 - 색종이

설명

도화지 위에 여러 장의 색종이를 붙였을 때, 전체 검은 영역의 넓이를 구하는 문제입니다.

도화지의 크기는 100 x 100 정사각형이며, 각 색종이는 10 x 10 크기의 정사각형입니다.

색종이는 도화지 내의 위치에 맞게 붙이며, 여러 장이 겹쳐서 붙을 수도 있습니다.

이때, 겹쳐진 영역은 중복해서 계산하지 않고, 실제로 도화지를 덮은 칸의 개수만을 넓이로 계산해야 합니다.

접근법

색종이로 인해 검게 칠해진 도화지의 영역을 계산하기 위해, 도화지를 좌표 격자처럼 생각할 수 있습니다.

각 색종이는 10칸씩 가로세로를 차지하므로, 해당 위치에 해당하는 영역을 순회하며 겹치지 않은 칸만 따로 계산합니다.

즉, 색종이를 하나씩 붙일 때마다 새롭게 덮이는 칸만 체크하여 넓이를 계산하고,

이미 이전 색종이로 덮여 있던 칸은 중복해서 세지 않도록 처리합니다.

색종이의 위치는 항상 도화지 범위 안에 주어지고, 최대 100장이기 때문에,

이 방식으로도 충분히 빠르게 전체 넓이를 구할 수 있습니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var board = new bool[100, 100];
    int count = int.Parse(Console.ReadLine());
    int area = 0;

    for (int i = 0; i < count; i++) {
      var tokens = Console.ReadLine().Split();
      int x = int.Parse(tokens[0]);
      int y = int.Parse(tokens[1]);

      for (int r = y; r < y + 10; r++) {
        for (int c = x; c < x + 10; c++) {
          if (!board[r, c]) {
            board[r, c] = true;
            area++;
          }
        }
      }
    }

    Console.WriteLine(area);
  }
}

C++

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

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

  bool back[100][100] = {};
  int cntP; cin >> cntP;

  int ans = 0;
  while (cntP--) {
    int x, y; cin >> x >> y;
    for (int i = y; i < y + 10; i++) {
      for (int j = x; j < x + 10; j++) {
        if (!back[i][j])
          back[i][j] = true, ans++;
      }
    }
  }

  cout << ans << "\n";
  return 0;
}