[프로그래머스] 네트워크 -Java

https://programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

import java.util.HashSet;
import java.util.Set;
class Solution {
		public int solution(int n, int[][] computers) {

			int[] parents = new int[n];

			make_set(parents, n);

			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (computers[i][j] == 1) {
						if (i == j)
							continue;
						union_set(i, j, parents);
					}
				}
			}

			Set<Integer> set = new HashSet<>();

			for (int i = 0; i < n; i++) {
				parents[i] = find_set(i, parents);
			}

			for (int i = 0; i < n; i++) {
				set.add(parents[i]);
			}

			return set.size();
		}

		private void union_set(int a, int b, int[] parents) {
			a = find_set(a, parents);
			b = find_set(b, parents);

			if (a != b)
				parents[b] = a;
		}

		private int find_set(int num, int[] parents) {
			if (parents[num] == num)
				return num;
			return find_set(parents[num], parents);
		}

		private void make_set(int[] parents, int n) {
			for (int i = 0; i < n; i++) {
				parents[i] = i;
			}
		}
	}

소요시간 : 25분

 

Union-Find 알고리즘을 사용하였습니다.

예전에 풀어봤던 문제인데 복습하려고 한번 더 풀어봤습니다.

 

make_set 함수는 자신의 부모를 모두 자신으로 만들어주는 역활을 합니다.

 

find_set 함수는 자신의 부모를 찾아주는 함수입니다.

 

union_set 함수는 노드를 연결해주는 함수입니다.

 

마지막에 find_set을 한번 더 실행해주는 이유는 

 

모든 노드가 자신의 바로 위에있는 부모만 가르키고 있기 때문에 자신의 최종부모로 값을 바꿔주기 위함입니다.

 

그리고 Set을 이용해 총 몇개의 네트워크가 연결되어있는지 확인했습니다.