[백준 29332] 보물 지도 (C#, C++) - soo:bak

문제 링크

29332번 - 보물 지도

설명

각 단서가 가리키는 방향을 만족하는 정수 격자점의 개수를 구하는 문제입니다.
가능한 위치가 무한히 많다면 Infinity를 출력합니다.

접근법

각 단서의 방향에 따라 보물이 있을 수 있는 범위를 좁혀갑니다. L은 왼쪽, R은 오른쪽, U는 위쪽, D는 아래쪽을 의미합니다.

단서 위치의 바로 옆 정수 좌표부터 범위에 포함되므로, 예를 들어 L이면 해당 x 좌표보다 1 작은 값이 x의 최댓값이 됩니다.

이후, x와 y 모두 최솟값과 최댓값이 정해져야 범위가 유한해집니다. 둘 중 하나라도 없으면 무한이고, 모두 있으면 각 축의 범위 크기를 곱한 값이 답입니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var parts = Console.In.ReadToEnd().Split();
    var idx = 0;
    var n = int.Parse(parts[idx++]);

    long lowerX = 0, upperX = 0, lowerY = 0, upperY = 0;
    bool hasLowerX = false, hasUpperX = false, hasLowerY = false, hasUpperY = false;

    for (var i = 0; i < n; i++) {
      var x = long.Parse(parts[idx++]);
      var y = long.Parse(parts[idx++]);
      var d = parts[idx++][0];

      if (d == 'L') {
        var v = x - 1;
        if (!hasUpperX || v < upperX) upperX = v;
        hasUpperX = true;
      } else if (d == 'R') {
        var v = x + 1;
        if (!hasLowerX || v > lowerX) lowerX = v;
        hasLowerX = true;
      } else if (d == 'U') {
        var v = y + 1;
        if (!hasLowerY || v > lowerY) lowerY = v;
        hasLowerY = true;
      } else {
        var v = y - 1;
        if (!hasUpperY || v < upperY) upperY = v;
        hasUpperY = true;
      }
    }

    if (!hasLowerX || !hasUpperX || !hasLowerY || !hasUpperY) {
      Console.WriteLine("Infinity");
      return;
    }

    long countX = upperX - lowerX + 1;
    long countY = upperY - lowerY + 1;
    Console.WriteLine(countX * countY);
  }
}

C++

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

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

  int n; cin >> n;
  ll lowerX = 0, upperX = 0, lowerY = 0, upperY = 0;
  bool hasLowerX = false, hasUpperX = false, hasLowerY = false, hasUpperY = false;

  for (int i = 0; i < n; i++) {
    ll x, y; char d;
    cin >> x >> y >> d;

    if (d == 'L') {
      ll v = x - 1;
      if (!hasUpperX || v < upperX) upperX = v;
      hasUpperX = true;
    } else if (d == 'R') {
      ll v = x + 1;
      if (!hasLowerX || v > lowerX) lowerX = v;
      hasLowerX = true;
    } else if (d == 'U') {
      ll v = y + 1;
      if (!hasLowerY || v > lowerY) lowerY = v;
      hasLowerY = true;
    } else {
      ll v = y - 1;
      if (!hasUpperY || v < upperY) upperY = v;
      hasUpperY = true;
    }
  }

  if (!hasLowerX || !hasUpperX || !hasLowerY || !hasUpperY) {
    cout << "Infinity\n";
    return 0;
  }

  ll countX = upperX - lowerX + 1;
  ll countY = upperY - lowerY + 1;
  cout << countX * countY << "\n";

  return 0;
}