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

문제설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

 

해결 방법

DFS(깊이우선탐색)를 이용해 영역을 구하는 문제이다.

 

DFS로 한 정점을 시작으로 갈 수 있는 모든 정점들을 한 영역이라고 쳤을 때, 영역의 개수를 구하는 문제이다.

 

[2020.04.04]

Union-Find를 사용해서 해결했다.

 

JAVA

class Solution {
    static boolean[] c;
    
    public static void dfs(int x, int n, int[][] computers){
        c[x] = true;
        
        for(int i = 0; i < n; i++){
            if(computers[x][i] == 1 && c[i] == false){
                dfs(i, n, computers);
            }
        }
    }
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        c = new boolean[n];
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(computers[i][j] == 1 && c[j] == false){
                    answer++;
                    dfs(j, n, computers);
                }
            }
        }
        return answer;
    }
}

 

package programmers;

import java.util.*;

public class p_43162 {
	static int[] parent;
	public static int find(int x) {
		if(x == parent[x]) return x;
		int y = find(parent[x]);
		parent[x] = y;
		return y;
	}
	
	public static void union(int x, int y) {
		x = find(x);
		y = find(y);
		
		if(x != y) parent[y] = x;
	}
	
	public static int solution(int n, int[][] a) {
		HashSet <Integer> set = new HashSet<>();
		parent = new int[n];
		for(int i = 0; i < n; i++) parent[i] = i;
		
		for(int i = 0; i < n; i++) {
			a[i][i] = 0;
			for(int j = 0; j < n; j++) {
				if(a[i][j] == 1) union(i, j);
			}
		}
		
		for(int i = 0; i < n; i++) set.add(find(parent[i]));
		
		return set.size();
	}
	public static void main(String[] args) {
		int n = 3;
		int[][] a = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
		
		
		System.out.println(solution(n, a));
	}
}