[백준 2519] 막대기 (C#, C++) - soo:bak

문제 링크

2519번 - 막대기

설명

각 학생이 3개의 막대기를 가지고 있을 때, 학생마다 최대 1개의 막대기만 제거하여 남은 모든 막대기가 서로 교차하지 않도록 만들 수 있는지 판정하는 문제입니다. 가능하다면 제거할 막대기 번호들을 출력합니다.

접근법

이 문제는 2-SAT으로 해결할 수 있습니다. 각 막대기에 대해 제거할지 말지를 결정해야 하는데, 여러 조건들이 서로 얽혀 있어서 모순 없이 모든 조건을 만족하는 선택이 존재하는지 판단해야 합니다.

먼저 각 막대기를 하나의 변수로 생각합니다. 변수가 참이면 그 막대기를 제거한다는 뜻이고, 거짓이면 남긴다는 뜻입니다.

첫 번째 조건은 학생별로 최대 1개만 제거할 수 있다는 것입니다. 한 학생이 가진 세 막대기 중 두 개 이상을 동시에 제거할 수 없습니다. 예를 들어 첫 번째 막대기를 제거하기로 했다면, 두 번째와 세 번째는 반드시 남겨야 합니다. 이 관계를 논리식으로 표현하면, 어떤 막대기를 제거하면 같은 학생의 다른 막대기들은 제거하지 않는다는 함의 관계가 됩니다.

두 번째 조건은 교차하는 막대기 쌍에 대한 것입니다. 두 막대기가 서로 교차한다면 둘 다 남길 수는 없습니다. 둘 중 적어도 하나는 제거해야 합니다. 이것도 함의 관계로 표현됩니다. 한 막대기를 남기기로 했다면 교차하는 다른 막대기는 반드시 제거해야 합니다.

이렇게 만들어진 함의 관계들을 방향 그래프로 나타냅니다. 각 변수와 그 부정을 정점으로 두고, 함의 관계를 간선으로 연결합니다. 그런 다음 강한 연결 요소를 구합니다.

만약 어떤 변수와 그 부정이 같은 강한 연결 요소에 속한다면, 그 변수는 참이면서 동시에 거짓이어야 한다는 모순이 발생합니다. 이 경우 조건을 만족하는 선택이 불가능합니다.

모순이 없다면 각 변수의 값을 결정합니다. 강한 연결 요소의 위상 순서에서 더 뒤에 나오는 쪽을 참으로 선택하면 모든 함의 관계를 만족하는 해가 됩니다. 참으로 선택된 막대기들이 제거 목록이 됩니다.

두 선분이 교차하는지는 외적을 이용해 판정합니다. 한 선분의 양 끝점이 다른 선분을 기준으로 서로 반대편에 있고, 그 역도 성립하면 두 선분은 교차합니다.

---

Code

C#

using System;
using System.Collections.Generic;
using System.Text;

class Program {
  struct Point { public int X, Y; }

  static int N, V; // V = 3N
  static List<int>[] g = Array.Empty<List<int>>();
  static List<int>[] rg = Array.Empty<List<int>>();
  static bool[] visited = Array.Empty<bool>();
  static int[] comp = Array.Empty<int>();
  static List<int> order = new();
  static Point[] p1 = Array.Empty<Point>(), p2 = Array.Empty<Point>();

  static int Not(int i) => i >= V ? i - V : i + V;

  static void AddEdge(int a, int b) {
    g[a].Add(b);
    g[Not(b)].Add(Not(a));
    rg[b].Add(a);
    rg[Not(a)].Add(Not(b));
  }

  static long Cross(Point a, Point b, Point c) =>
    1L * (b.X - a.X) * (c.Y - a.Y) - 1L * (b.Y - a.Y) * (c.X - a.X);

  static bool IsCross(int i, int j) {
    long cp1 = Cross(p1[i], p2[i], p1[j]) * Cross(p1[i], p2[i], p2[j]);
    long cp2 = Cross(p1[j], p2[j], p1[i]) * Cross(p1[j], p2[j], p2[i]);
    return cp1 < 0 && cp2 < 0;
  }

  static void Dfs1(int vtx) {
    visited[vtx] = true;
    foreach (var nx in g[vtx]) if (!visited[nx]) Dfs1(nx);
    order.Add(vtx);
  }

  static void Dfs2(int vtx, int c) {
    comp[vtx] = c;
    foreach (var nx in rg[vtx]) if (comp[nx] == 0) Dfs2(nx, c);
  }

  static void Main() {
    N = int.Parse(Console.ReadLine()!);
    V = 3 * N;
    p1 = new Point[V];
    p2 = new Point[V];
    for (var i = 0; i < V; i++) {
      var parts = Console.ReadLine()!.Split();
      p1[i].X = int.Parse(parts[0]); p1[i].Y = int.Parse(parts[1]);
      p2[i].X = int.Parse(parts[2]); p2[i].Y = int.Parse(parts[3]);
    }

    var nodes = 2 * V;
    g = new List<int>[nodes];
    rg = new List<int>[nodes];
    for (var i = 0; i < nodes; i++) { g[i] = new(); rg[i] = new(); }

    for (var s = 0; s < N; s++) {
      var a = 3 * s;
      var b = a + 1;
      var c = a + 2;
      AddEdge(a, Not(b)); AddEdge(a, Not(c));
      AddEdge(b, Not(a)); AddEdge(b, Not(c));
      AddEdge(c, Not(a)); AddEdge(c, Not(b));
    }

    for (var i = 0; i < V; i++) {
      for (var j = i + 1; j < V; j++) {
        if (IsCross(i, j)) AddEdge(Not(i), j);
      }
    }

    visited = new bool[nodes];
    for (var i = 0; i < nodes; i++) if (!visited[i]) Dfs1(i);

    comp = new int[nodes];
    var cid = 1;
    for (var idx = order.Count - 1; idx >= 0; idx--) {
      var vtx = order[idx];
      if (comp[vtx] == 0) Dfs2(vtx, cid++);
    }

    for (var i = 0; i < V; i++) {
      if (comp[i] == comp[Not(i)]) { Console.WriteLine("-1"); return; }
    }

    var ans = new List<int>();
    for (var i = 0; i < V; i++) {
      if (comp[i] > comp[Not(i)]) ans.Add(i + 1);
    }

    var sb = new StringBuilder();
    sb.AppendLine(ans.Count.ToString());
    if (ans.Count > 0) sb.AppendLine(string.Join(" ", ans));
    Console.Write(sb.ToString());
  }
}

C++

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

struct Point { int x, y; };

int N, V;
vvi g, rg;
vi order, comp;
vector<bool> vis;
vector<Point> p1, p2;

int Not(int i) { return i >= V ? i - V : i + V; }

void addEdge(int a, int b) {
  g[a].push_back(b);
  g[Not(b)].push_back(Not(a));
  rg[b].push_back(a);
  rg[Not(a)].push_back(Not(b));
}

ll cross(const Point& a, const Point& b, const Point& c) {
  return 1LL * (b.x - a.x) * (c.y - a.y) - 1LL * (b.y - a.y) * (c.x - a.x);
}

bool isCross(int i, int j) {
  ll cp1 = cross(p1[i], p2[i], p1[j]) * cross(p1[i], p2[i], p2[j]);
  ll cp2 = cross(p1[j], p2[j], p1[i]) * cross(p1[j], p2[j], p2[i]);
  return cp1 < 0 && cp2 < 0;
}

void dfs1(int v) {
  vis[v] = true;
  for (int nx : g[v]) if (!vis[nx]) dfs1(nx);
  order.push_back(v);
}

void dfs2(int v, int c) {
  comp[v] = c;
  for (int nx : rg[v]) if (comp[nx] == 0) dfs2(nx, c);
}

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

  cin >> N;
  V = 3 * N;
  p1.resize(V); p2.resize(V);
  for (int i = 0; i < V; i++)
    cin >> p1[i].x >> p1[i].y >> p2[i].x >> p2[i].y;

  int nodes = 2 * V;
  g.assign(nodes, {});
  rg.assign(nodes, {});

  for (int s = 0; s < N; s++) {
    int a = 3 * s, b = a + 1, c = a + 2;
    addEdge(a, Not(b)); addEdge(a, Not(c));
    addEdge(b, Not(a)); addEdge(b, Not(c));
    addEdge(c, Not(a)); addEdge(c, Not(b));
  }

  for (int i = 0; i < V; i++) {
    for (int j = i + 1; j < V; j++) {
      if (isCross(i, j)) addEdge(Not(i), j);
    }
  }

  vis.assign(nodes, false);
  for (int i = 0; i < nodes; i++) if (!vis[i]) dfs1(i);

  comp.assign(nodes, 0);
  int cid = 1;
  for (int i = (int)order.size() - 1; i >= 0; i--) {
    int v = order[i];
    if (comp[v] == 0) dfs2(v, cid++);
  }

  for (int i = 0; i < V; i++) {
    if (comp[i] == comp[Not(i)]) { cout << -1 << "\n"; return 0; }
  }

  vi ans;
  for (int i = 0; i < V; i++) if (comp[i] > comp[Not(i)]) ans.push_back(i + 1);

  cout << ans.size() << "\n";
  if (!ans.empty()) {
    for (int i = 0; i < (int)ans.size(); i++)
      cout << ans[i] << (i + 1 == (int)ans.size() ? '\n' : ' ');
  }

  return 0;
}