본문 바로가기

알고리즘 관련/BOJ

BOJ)3136 평면도

문제: icpc.me/3136

좌표평면에 주어진 순서대로 그림을 그릴 때 평면도 상에서 존재하는 모든 방의 개수를 출력하는 문제이다.

평면 그래프에서 V-E+F=2 라는 공식이 성립한다는 점을 이용하여 문제를 해결할 수 있다.(V:정점의 수, E:간선의 수,F:평면의 수)

구해야 하는게 평면의 수 이므로 평면의 수는 F=2-V+E로 구할 수 있다. 하지만 좌표 평면 전체도 하나의 평면으로 세므로 답은 1-V+E가 된다.

이제 V의 수와 E의 수를 구해야 하는데 이는 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
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
int dx[8= { 0,1,1,1,0,-1,-1,-};
int dy[8= { 1,1,0,-1,-1,-1,0,};
set<pair<intint>> vertex;
set<pair<pair<intint>, pair<intint>>> edge;
int n, x, y;
int main() {
    scanf("%d"&n);
    vertex.insert({ x,y });
    for (int i = 0; i < n; i++) {
        int k;
        scanf("%1d"&k);
        for (int j = 0; j < 2; j++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            pair<intint> s = { x,y };
            pair<intint> e = { nx,ny };
            if (s < e)swap(s, e);
            edge.insert({ s,e });
            x = nx, y = ny;
            vertex.insert({ x,y });
        }
    }
    printf("%d\n"- vertex.size() + edge.size());
    return 0;
}
cs


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

BOJ)14936 엘리베이터 장난  (0) 2017.12.04
BOJ)11670 초등 수학  (0) 2017.11.15
BOJ)14195 DotB  (0) 2017.11.15
BOJ)14748 Flow Graph Complexity  (0) 2017.10.24
BOJ)5846 Tractor  (0) 2017.10.24