BOJ)3136 평면도

문제: icpc.me/3136

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

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

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

이제 V의 수와 E의 수를 구해야 하는데 이는 set을 이용하여 세주면 편리하게 계산할 수 있다.

이 때 주의해야 할 점이 대각선으로 만나는 점을 처리해주기 위해 한 방향으로 나아갈 때 두번씩 나아가도록 점을 찍어주어야 한다. 

자세한 것은 소스를 보며 이해하도록 하자.

#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
int dx[8] = { 0,1,1,1,0,-1,-1,-1 };
int dy[8] = { 1,1,0,-1,-1,-1,0,1 };
set<pair<int, int>> vertex;
set<pair<pair<int, int>, pair<int, int>>> 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<int, int> s = { x,y };
            pair<int, int> e = { nx,ny };
            if (s < e)swap(s, e);
            edge.insert({ s,e });
            x = nx, y = ny;
            vertex.insert({ x,y });
        }
    }
    printf("%d\n", 1 - vertex.size() + edge.size());
    return 0;
}