3136 - 평면도

여기를 클릭해 주세요.

문제 링크

---

 

https://www.acmicpc.net/problem/3136

 

 

문제 요약

---

 

문제에서 주어진 방향대로 선을 그어나갔을 때 생기는 평면의 개수를 출력하는 문제.

 

 

문제 풀이

 

 

 

 

---

 

 

이 문제를 처음 본다면 당황할 수 있다. 언제 공간이 생기는지 아는것도 힘들 뿐더러 그걸 알았다고 하더라도 공간을 어떻게 세어야 할지 막막하기 때문이다.

하지만 정수 좌표를 버텍스라고 생각하고, 선들을 엣지라고 생각한다면 그래프에서의 평면의 개수를 찾는 문제로 치환이 된다. 일반적으로 그래프에서 평면의 개수를 찾는것은 어렵지만 선을 그어서 생기는 그래프는 평면그래프 라는것을 깨닫는 순간 문제는 매우 쉬워진다. 평면그래프에는 아래와 같은 공식이 있다.

 

\(V\ -\ E\ +\ F\ =\ 2\)

 

\(V\)은 버텍스의 개수, \(E\)는 엣지의 수, \(F\)는 그래프에 존재하는 평면의 개수이다. 이 공식을 이용하면 바로 답을 구할 수 있다.

버텍스와 엑지는 \(set\)을 이용해 효율적으로 관리할 수 있다.

 

다만 대각선으로 만나는 점을 잘 처리해야 된다. 대각선끼리 만나는 엣지는 소수점 위치에서 교차점이 생기기 때문이다. 이는 좌표를 2배씩 늘리는 방법을 이용해 쉽게 해결할 수 있다.

 

그리고 최종적으로 구한 \(F\)의 개수에서는 1을 빼줘야한다. 위 공식에서 \(F\)는 그래프 외부에 생기는 큰 평면도 포함을 하고있기 때문이다.

 

 

소스 코드

 

 

 

 

---

 

 

#include <stdio.h> #include <set> #include <algorithm>  using namespace std;  const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1}; const int dy[] = ; int n, x, y; char A[100010]; set<pair<int, int>> vertex; set<pair<pair<int, int>, pair<int, int>>> edge;  int main() {   scanf("%d%s", &n, A);   vertex.insert();   for (int i = 0 ; i < n ; ++i) {     int dir = A[i] - '0';     for (int j = 0 ; j < 2 ; ++j) {       int nx = x + dx[dir], ny = y + dy[dir];       pair<int, int> s = ;       pair<int, int> e = ;       if (e < s) {         swap(s, e);       }       vertex.insert();       edge.insert();       x = nx;       y = ny;     }   }   int ans = 2 - (int)vertex.size() + (int)edge.size();   printf("%d\n", ans - 1); }