프로그래머스 네트워크 JAVA

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

문제

해당 문제는 컴퓨터의 개수와 컴퓨터 간 연결된 정보가 주어졌을 때 연결된 그룹이 몇 그룹인지 구하면 되는 문제다.

조건

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

풀이

해당 문제는 처음에는 bfs를 이용하여 해결하여하였으나 문제를 잘못 이해한 걸 알게 되었고 union find를 이용해 쉽게 해결할 수 있었다. union을 통해 컴퓨터를 연결해주면서 숫자가 작은 컴퓨터가 상위 루트를 차지하도록 갱신해주었고 최종적으로 자기 자신을 가리키는 경우가 하나의 그룹이므로 개수를 카운트해 리턴해주는 방식으로 해결했다.

코드

class Solution {
    static int[] number; // 연결 정보 배열

	public static int solution(int n, int[][] computers) {
		int answer = 0;
		number = new int[n + 1]; 
		for (int i = 1; i <= n; i++) { // 처음에는 자기 자신을 루트로 가르킴
			number[i] = i;
		}

		for (int i = 0; i < n; i++) { // 반복문을 돌면서 연결되어있고, 자기 자신이 아니고 루트가 다른경우 둘을 nuion
			for (int j = 0; j < n; j++) {
				if (computers[i][j] == 1 && i != j && find(i + 1) != find(j + 1))
					union(i + 1, j + 1);
			}
		}
		for (int i = 1; i <= n; i++) { // 모두 union 끝나면 자기 자신을 가리키는 곳이 그룹의 대빵이므로 갯수를 카운트함
			if (number[i] == i) {
				answer++;
			}
		}
		return answer;
	}

	public static int find(int a) {
		if (a == number[a])
			return a;
		return number[a] = find(number[a]);
	}

	public static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if (a < b)
			number[b] = a;
		else
			number[a] = b;
	}
}

 

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드