-
[KATTIS] Grid MST
Grid MST 풀이 문제가 좋아서 가져왔다. 1000*1000 크기의 격자에 N(100,000)개의 점이 있다. 모든 점쌍 사이에 가중치가 w(두 점 사이의 맨하탄 거리)인 간선이 있다. 이 때, 이 그래프에서 만들 수 있는 MST의 최소 가중치 합은? 정점 10만개짜리 완전그래프이기에, 나이브한 방법으로 문제를 풀기에는 꽤나 어려워 보인다. MST를 구성하는 상황을 생각해 보자. a-b와 b-c가 있고, b를 지나는 것이 최단인 a-c가 존재한다면, a-c를 MST에 포함시키는 것 보다 더 나은 방법(a-b, b-c)이 항상 존재한다. 격자의 크기가 최대 1000*1000임에 주목하자. 우리는...
-
[BOJ] 3108 : 로고
3108 : 로고 풀이 사각형을 하나의 노드로 보자. 어떤 두 사각형 a, b가 겹친다면 두 사각형은 연결된 것으로 생각하자. 연결된 사각형들은 연필을 들지 않고 삥삥 돌며 잘 그릴 수 있다. 연필은 연결 요소의 개수 - 1번 들어주면 된다. 단, 시작점인 (0, 0)을 지나는 경우의 예외처리를 잘 해주자. (x1=0, y1=0, x2=0, y2=0)인 경우도 비교해주면 된다. Flood fill로 풀어도 된다. 코드 #include <cstdio> #include <algorithm> #define y1 fu using namespace std; const int n_ = 1000 +...