[BOJ 3136] 평면도

2021년 5월 28일

문제는 여기서 풀 수 있습니다.

문제 요약

문제에서 주어진 방향대로 이차원 좌표 평면에 선을 그었을 때 생긴 면의 개수를 구하는 문제입니다.

문제 풀이

이차원 좌표 평면에 선을 그어 생기는 도형은 그래프로 만들 수 있습니다. 그리고 이차원 좌표 평면에 만들어진 그래프는 평면 그래프가 될 수 있습니다. 이때 평면 그래프의 오일러 지표는 2라는 성질을 이용하면 문제를 풀 수 있습니다.

오일러 지표는 정점의 수, 간선의 수, 면의 수로 표현할 수 있으며 아래와 같습니다.

v - e + f = 2

$v$ 는 정점의 수, $e$ 는 간선의 수, $f$ 는 면의 수 입니다. 문제에서 주어진 방향대로 선을 그으며 그래프를 만들면 $v$ 와 $e$ 를 이용해 $f$ 를 구할 수 있습니다. 이때 $f$ 는 바깥의 열린 면도 포함하고 있기 때문에 $f$ 에서 1을 뺀 값이 문제의 답입니다.

선을 긋다 보면 대각선으로 교차하는 점이 좌표가 소수점이기 때문에 관리하기가 까다롭습니다. 이런 경우에는 좌표 평면을 두 배 확장해 정수 좌표로 바꿔 좀 더 쉽게 관리할 수 있습니다.

실제 구현에서 set을 이용해 정점과 간선들의 집합을 중복 없이 관리할 수 있고 시간 복잡도는 $O(NlogN)$ 입니다.

#include <stdio.h>
#include <set>
#include <algorithm>

using namespace std;

typedef pair<int, int> Point;
typedef pair<Point, Point> Edge;

const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
int n;
char directions[100010];
set<Point> vertices;
set<Edge> edges;

int main() {
	scanf("%d%s", &n, directions);

	int cx = 0, cy = 0;
	vertices.insert({ cx, cy });

	for (int i = 0 ; i < n ; ++i) {
		int direction = directions[i] - '0';

		for (int j = 0 ; j < 2 ; ++j) {
			int nx = cx + dx[direction], ny = cy + dy[direction];

			Point cp = { cx, cy };
			Point np = { nx, ny };
			Edge edge = cp < np ? make_pair(cp, np) : make_pair(np, cp);

			vertices.insert(np);
			edges.insert(edge);

			cx = nx;
			cy = ny;
		}
	}

	int ans = 2 - (int)vertices.size() + (int)edges.size();
  	printf("%d\n", ans - 1);
}