문제설명
.
DFS/BFS로 분류되어있는 문제지만, union-find로 풀었습니다.
연결된 컴퓨터들끼리 union해주고 몇개의 집합으로 나눠지는지 갯수를 세어주면 되는 특이사항 없는(?)문제 입니다.
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | #include <string> #include <vector> using namespace std; int parent[201]; bool pa[201]; int findparent(int a) { if (parent[a] == a) return a; return parent[a] = findparent(parent[a]); } void unionparent(int a, int b) { a = findparent(a); b = findparent(b); if (a < b) parent[b] = a; else parent[a] = b; } int solution(int n, vector<vector<int> > computers) { int answer = 0; for (int i = 0; i < n; i++) { parent[i] = i; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (computers[i][j] == 1) { unionparent(i,j); } } } for(int i = 0; i < n; i++) parent[i] = findparent(i); for (int i = 0; i < n; i++) { if (!pa[parent[i]]) { pa[parent[i]] = true; answer++; } } return answer; } | cs |
