pstopia Notes for Problem Solving Contest

[Easy] RectangleArea

Topcoder SRM 505 Div1

Problem

S(i,j) = xi * yj 라는 정보가 주어지면 이것을 xi = S(i,j) / yj 로 바꾸거나 yj = S(i,j) / xi 로 바꿔서 다른 식에 대입하면 필요한 변수의 개수가 하나 줄어드는 효과가 있다. xi 와 yj 를 정점으로 만들고 이렇게 정보가 주어진 노드 사이에는 간선을 이은 그래프를 생각해볼 수 있다. 여기서 연결 컴포넌트는 서로간의 변수 변환을 통해 변수의 값을 구하거나 하나의 변수로 나타낼 수 있는 집합을 나타낸다. 그럼 전체 그래프 상에서 컴포넌트들을 모두 연결하면, 전체 넓이의 값을 구하거나 전체 넓이를 하나의 변수 나타낼 수 있게 된다. 여기에 전체넓이 = sum(xi * yj) 식을 연립하면 전체넓이를 항상 구할 수 있다. 따라서 컴포넌트들을 모두 연결하는 최소의 간선수가 답이 된다.
#include <vector>
using namespace std;
bool visit[120];
vector<int> graph[120];
void dfs(int u) {
visit[u] = true;
for (int v : graph[u]) {
if (!visit[v]) {
dfs(v);
}
}
}
class RectangleArea {
public:
int minimumQueries(vector<string> known) {
int n = known.size();
int m = known[0].length();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (known[i][j] == 'Y') {
graph[i].push_back(n + j);
graph[n + j].push_back(i);
}
}
}
int component = 0;
for (int i = 0; i < n + m; ++i) {
if (!visit[i]) {
++component;
dfs(i);
}
}
return component - 1;
}
};