풀이 과정
문제를 딱 보자마자 유니온 파인드 알고리즘이 생각났다.
풀고보니 유니온 파인드의 기본적인 문제이며, 부모 노드의
중복되지 않은 숫자의 개수는 몇 개인지 세면 되는 단순한 문제였다.
풀이 1
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int parent[201];
int getParent(int x){
if(parent[x] == x) return x;
return parent[x] = getParent(parent[x]);
}
void UnionParent(int a, int b){
a = getParent(a);
b = getParent(b);
if(a > b) parent[a] = b;
else parent[b] = a;
}
int solution(int n, vector<vector<int>> computers) {
int answer = 0;
for(int i = 1; i <= n; i++){
parent[i] = i;
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i != j){
if(computers[i][j] == 1) UnionParent(i + 1, j + 1);
}
}
}
vector<int> v;
for(int i = 1; i <= n; i++){
v.push_back(getParent(i));
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
answer = v.size();
return answer;
}
풀이 2
#include <string>
#include <vector>
using namespace std;
int parent[201];
int getParent(int x){
if(parent[x] == x) return x;
return parent[x] = getParent(parent[x]);
}
void UnionParent(int a, int b){
a = getParent(a);
b = getParent(b);
if(a > b) parent[a] = b;
else parent[b] = a;
}
int solution(int n, vector<vector<int>> computers) {
int answer = 0;
for(int i = 1; i <= n; i++){
parent[i] = i;
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i != j){
if(computers[i][j] == 1) UnionParent(i + 1, j + 1);
}
}
}
vector<int> v;
for(int i = 1; i <= n; i++){
v.push_back(getParent(i));
}
// sort 오름차순 구현
for(int i = 0; i < v.size(); i++){
for(int j = 0; j < v.size() - 1; j++){
if(v[j] > v[j + 1]){
int temp = v[j];
v[j] = v[j + 1];
v[j + 1] = temp;
}
}
}
// erase, unique 함수 구현
int num = 1;
int temp[201];
temp[0] = v[0];
for(int i = 1; i < v.size(); i++){
if(v[i] != temp[num - 1]){
temp[num++] = v[i];
}
}
answer = num;
return answer;
}
'🍞 Algorithm > Programmers' 카테고리의 다른 글
[프로그래머스][Level3] 베스트앨범 c++ (0) | 2024.02.22 |
---|---|
[프로그래머스][Level2] 다리를 지나는 트럭 c++ (0) | 2024.02.21 |
[프로그래머스][Level3] 가장 먼 노드 c++ (0) | 2022.10.21 |
[프로그래머스][Level2] 행렬의 곱셈 c++ (0) | 2022.10.21 |
[프로그래머스][Level2] 피로도 c++ (0) | 2022.10.21 |