백준3136 평면도

작성일 | In

문제 링크

  • http://icpc.me/3136

문제 출처

  • 2008 COI Final Exam #2 1번

시간복잡도

  • $O(N \log N)$

풀이

문제에 나온 방식대로 열심히 움직여주면 평면 그래프가 만들어지게 됩니다.
두 선분이 격자점이 아닌 곳에서 교차할 수도 있는데, 그런 점은 항상 .5 단위이기 때문에 각 이동마다 2칸씩 이동해주면 아무 지장이 없습니다.

연결 평면 그래프에서는 V-E+F=2 가 성립합니다. ()평면 그래프의 면의 개수 - 1)을 출력하면 되므로 1+E-V를 출력하면 됩니다.

정점 개수 V와 간선 개수 E는 쉽게 구할 수 있기 때문에 설명을 생략하겠습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> p;
typedef pair<p, p> pp;
const int di[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dj[] = {0, 1, 1, 1, 0, -1, -1, -1};

set<p> nd;
set<pp> edg;

int solution(vector<int> arr) {
    int n = arr.size();
    p t = {0, 0}; nd.insert(t);
    for(auto i : arr) for(int j=0; j<2; j++){
            int x = t.x + di[i];
            int y = t.y + dj[i];
            p prv = t; t = {x, y};
            nd.insert(t);
            edg.insert({min(prv, t), max(prv, t)});
        }
    return edg.size() - nd.size() + 1;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n; vector<int> v(n);
    for(int i=0; i<n; i++){
        char c; cin >> c; v[i] = c - '0';
    }
    cout << solution(v);
}