[백준 3108] 로고 (C#, C++) - soo:bak

문제 링크

3108번 - 로고

설명

N개의 직사각형 테두리를 거북이가 그릴 때, 펜을 올리는 명령 PU의 최소 횟수를 구하는 문제입니다. 거북이는 (0, 0)에서 펜이 내려진 상태로 시작하며, 같은 선은 여러 번 그릴 수 있지만 주어진 선 외에는 그릴 수 없습니다.

접근법

먼저, 테두리들이 서로 연결되어 있으면 펜을 올리지 않고 이어서 그릴 수 있습니다. 따라서 이 문제는 테두리 선분들의 연결 요소 개수를 세는 문제로 바꿀 수 있습니다.

다음으로, 선분의 겹침과 인접을 정확히 처리하기 위해 좌표를 2배로 확장합니다. 좌표 범위가 -500에서 500이므로 500을 더해 양수로 만든 뒤 2를 곱합니다. 이렇게 하면 격자 크기는 2001 곱하기 2001이 됩니다.

이후, 각 직사각형의 네 변을 격자에 표시하고 DFS로 연결 요소 개수를 셉니다. 시작점 (0, 0)이 어떤 연결 요소에 포함되어 있다면 그 요소는 펜을 올리지 않고 시작할 수 있으므로 개수에서 1을 뺍니다.

---

Code

C#

using System;
using System.Collections.Generic;

class Program {
  const int MAT_MAX = 2001;
  const int COORD_MAX = 500;

  static int[,] mat = new int[MAT_MAX, MAT_MAX];
  static readonly int[] dirX = { 0, 0, 1, -1 };
  static readonly int[] dirY = { 1, -1, 0, 0 };

  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    for (var i = 0; i < n; i++) {
      var s = Console.ReadLine()!.Split();
      var x1 = (int.Parse(s[0]) + COORD_MAX) * 2;
      var y1 = (int.Parse(s[1]) + COORD_MAX) * 2;
      var x2 = (int.Parse(s[2]) + COORD_MAX) * 2;
      var y2 = (int.Parse(s[3]) + COORD_MAX) * 2;

      for (var j = x1; j <= x2; j++) {
        mat[y1, j] = 1;
        mat[y2, j] = 1;
      }
      for (var j = y1; j <= y2; j++) {
        mat[j, x1] = 1;
        mat[j, x2] = 1;
      }
    }

    var ans = 0;
    for (var i = 0; i < MAT_MAX; i++) {
      for (var j = 0; j < MAT_MAX; j++) {
        if (mat[i, j] == 1) {
          DFS(i, j);
          ans++;
        }
      }
    }

    if (mat[2 * COORD_MAX, 2 * COORD_MAX] == 2) ans--;
    Console.WriteLine(ans);
  }

  static void DFS(int sy, int sx) {
    var stack = new Stack<(int y, int x)>();
    stack.Push((sy, sx));
    mat[sy, sx] = 2;
    while (stack.Count > 0) {
      var (y, x) = stack.Pop();
      for (var i = 0; i < 4; i++) {
        var ny = y + dirY[i];
        var nx = x + dirX[i];
        if (ny < 0 || nx < 0 || ny >= MAT_MAX || nx >= MAT_MAX) continue;
        if (mat[ny, nx] == 2 || mat[ny, nx] == 0) continue;
        mat[ny, nx] = 2;
        stack.Push((ny, nx));
      }
    }
  }
}

C++

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

const int MAT_MAX = 2001;
const int COORD_MAX = 500;

int mat[MAT_MAX][MAT_MAX];
int dirX[4] = {0, 0, 1, -1}, dirY[4] = {1, -1, 0, 0};

void dfs(int y, int x) {
  if (y < 0 || x < 0 || y >= MAT_MAX || x >= MAT_MAX) return;
  if (mat[y][x] == 2 || !mat[y][x]) return;
  mat[y][x] = 2;
  for (int i = 0; i < 4; i++)
    dfs(y + dirY[i], x + dirX[i]);
}

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

  int n; cin >> n;
  for (int i = 0; i < n; i++) {
    int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
    x1 = (x1 + COORD_MAX) * 2;
    y1 = (y1 + COORD_MAX) * 2;
    x2 = (x2 + COORD_MAX) * 2;
    y2 = (y2 + COORD_MAX) * 2;
    for (int j = x1; j <= x2; j++) {
      mat[y1][j] = 1;
      mat[y2][j] = 1;
    }
    for (int j = y1; j <= y2; j++) {
      mat[j][x1] = 1;
      mat[j][x2] = 1;
    }
  }

  int ans = 0;
  for (int i = 0; i < MAT_MAX; i++) {
    for (int j = 0; j < MAT_MAX; j++) {
      if (mat[i][j] == 1) {
        dfs(i, j);
        ans++;
      }
    }
  }

  if (mat[2 * COORD_MAX][2 * COORD_MAX] == 2) ans--;
  cout << ans << "\n";

  return 0;
}