티스토리 뷰

알고리즘 관련/BOJ

BOJ)11975 Build Gates

JASON 자손9319 2017. 1. 18. 19:44

문제: icpc.me/11975


펜스를 동서남북으로 치려고 할 때 펜스로 인하여 닫힌 구간은 나가야 할 문이 필요하다고 할 때 문의 최소 개수를 출력하는 문제이다.


문제를 다시 해석하자면 그래프를 그린 뒤 완전히 닫혀있는 구간의 개수를 세는것이다.


즉 평면의 개수를 찾는 문제인데, 선을 그어서 생긴 그래프이므로 평면그래프가 되니 V-E+F=2라는 공식을 이용하여


F=2-V+E로 평면의 개수를 구할 수 있다.


이때 그래프 전체가 평면의 개수에 포함되기 때문에 F-1을 출력해주면 된다.


Vertex와 Edge는 중복이 되면 안되므로 set을 통하여 관리해주면 된다.


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
35
36
37
38
39
#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
#include <set>
#include <map>
using namespace std;
int n, r, x, y;
string a;
int dx[] = { 0,0,1,-};
int dy[] = { 1,-1,0,};
set<pair<intint>> vertex;
set<pair<pair<intint>, pair<intint>>> edge;
map<char,int> mp;
int main() {
    mp['N'= 0;
    mp['S'= 1;
    mp['E'= 2;
    mp['W'= 3;
    vertex.insert({ x,y });
    scanf("%d"&n);
    cin >> a;
    for (int i = 0; i < a.length(); i++) {
        int idx = mp[a[i]];
        int cx = dx[idx] + x;
        int cy = dy[idx] + y;
        pair<intint> s = { x,y };
        pair<intint> e = { cx,cy };
        if (e < s)
            swap(s, e);
        vertex.insert({ cx,cy });
        edge.insert({ s,e });
        x = cx;
        y = cy;
    }
    r = - vertex.size() + edge.size();
    printf("%d", r);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)4343 Arctic Network  (0) 2017.01.19
BOJ)13325 이진 트리  (1) 2017.01.18
BOJ)11975 Build Gates  (0) 2017.01.18
BOJ)11974 Subsequences Summing to Sevens  (0) 2017.01.18
BOJ)11973 Angry Cows  (0) 2017.01.18
BOJ)10216 Count Circle Groups  (0) 2017.01.17
댓글
댓글쓰기 폼