[Easy] RectangleArea
Topcoder SRM 505 Div1
S(i,j) = xi * yj 라는 정보가 주어지면 이것을 xi = S(i,j) / yj 로 바꾸거나 yj = S(i,j) / xi 로 바꿔서 다른 식에 대입하면
필요한 변수의 개수가 하나 줄어드는 효과가 있다.
xi 와 yj 를 정점으로 만들고 이렇게 정보가 주어진 노드 사이에는 간선을 이은 그래프를 생각해볼 수 있다.
여기서 연결 컴포넌트는 서로간의 변수 변환을 통해 변수의 값을 구하거나 하나의 변수로 나타낼 수 있는 집합을 나타낸다.
그럼 전체 그래프 상에서 컴포넌트들을 모두 연결하면, 전체 넓이의 값을 구하거나 전체 넓이를 하나의 변수 나타낼 수 있게 된다.
여기에 전체넓이 = sum(xi * yj) 식을 연립하면 전체넓이를 항상 구할 수 있다.
따라서 컴포넌트들을 모두 연결하는 최소의 간선수가 답이 된다.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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; | |
| } | |
| }; |