그래프 연결 확인하는 법

그래프 연결 확인하는 법

1. 유니온 파인드

    static void makeset() {
    	parent = new int[islandCnt];
    	
    	for (int i = 1; i < islandCnt; i++) parent[i] = i;
    }
    
    static int find(int node) {
    	if (node == parent[node]) return parent[node];
    	return parent[node] = find(parent[node]);
    }
    
    static void union(int node, int new_node) {
    	int p = find(node);
    	int new_p = find(new_node);
    	parent[p] = new_p;
    }

makeset => 자기 자신을 부모로 하는 배열을 만든다.
find => 자기 자신의 부모 노드를 찾는 함수로서, 재귀함수를 이용하여 찾는다.
기저조건은 자기자신이 부모일 때 해당 값을 리턴해주면 된다.
union은 합치려는 node의 부모노드와 new_node의 부모노드를 합치면 된다.

2. 플로이드 워셜

static void floyd() {
    	for (int mid = 1; mid < islandCnt; mid++) {
    		for (int from = 1; from < islandCnt; from++) {
    			if (mid == from) continue;
    			for (int to = 1; to < islandCnt; to++) {
    				if (mid == to) continue;
    				
    				path[from][to] = Math.min(path[from][to], path[from][mid] + path[mid][to]);
    			}
    		}
    	}
    }

플로이드 워셜을 사용하게 되면 연결이 안된 부분은 최대값으로 될 것이다. 그래서 특정 노드 기준으로 다른 노드 사이에 거리가 최대값이 없으면 전부 연결 된 것으로 판단할 수 있다.