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

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

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

문제풀이

보자마자 Union-find 알고리즘이 생각나서 Level3 치고는 쉽게 풀었다.

그러나 마지막에 고려하지 않은 한가지가 있었다. 

먼저 1와 2의 부모가 3으로 연결 되었고

다음으로는 4와 5의 부모가 6이 되었을때는 2개의 네트워크이지만 마지막에 3과 6의 부모가 생겨버리면 네트워크는 1이 되어 버린다. 그래서 마지막에 네트워크를 찾을때 반복문 parents[i]로 찾아 버리면 틀린 답이 나온다. 이에 parents[i]로 찾는것이 아닌 for문을 돌면서 check[find(i)]로 부모를 통일 시켜 주면서 네트워크 갯수를 찾아야 한다.

코드

class Solution {
  int[] parents;
	
	public int solution(int n, int[][] computers) {
		make(n);
        
		for(int i = 0; i<n; i++) {
			for(int j =0; j<n; j++) {
				if(i==j) continue;
				if(computers[i][j] == 1) union(i,j);
			}
		}
		
		int[] check = new int[n];
		
		for(int i =0; i<n; i++) {
			check[find(i)] ++;
		}
		
		int answer= 0;
		for(int i =0; i<n; i++) {
			if(check[i] > 0) answer++; 
		}
        
        return answer;
    }
	
	private int find(int a) {
		if (parents[a] == a) return a;
		
		return parents[a] = find(parents[a]);
	}
	
	private void union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		
		if ( aRoot == bRoot) return;
		
		parents[bRoot] = aRoot;
		return;
	}

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