연결된 그래프 합쳐졌는지 체크 (feat. 행성 터널 문제)

문제를 풀다보면 엣지와 간선이 주어졌을 때 가중치에 따른 간선선택상황이 올 수 있다.

간선 정보들이 매우 많을 때 적절히 정렬되어 있다고 가정했을 때, 필요없는 간선인지 판단하는 것과,

간선 선택시 상황을 기억하고 있는 정보들을 업데이트를 해야할 것이다. 

 

ex) 0 -1 , (2-3, 3-4) 로 연결되어 있었고 1-4간선을 발견하였다.

1-4 연결이 되면 두 집합이 하나로 합쳐졌다고 정보를 수정해야 한다.

parent = new int[N]; //parent[i] = i 라고 생각

while (!queue.isEmpty()) {
			Edge tmp = queue.poll();
			
			if (!isSameParent(tmp.s, tmp.d)) {
			System.out.println(tmp.s + " " + tmp.d);
			System.out.print(Arrays.toString(parent) + "->" );
                	answer += tmp.score;
                	union(tmp.s, tmp.d);
               		System.out.println(Arrays.toString(parent));
			}
			
		}
////////////////////////////////////////////////////////////////////////////
    private static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a > b) parent[a] = b;
        else parent[b] = a;
    }

    private static int find(int a) {
        if (parent[a] == a) return a;
        else return parent[a] = find(parent[a]);
    }

    private static boolean isSameParent(int a, int b) {
        return find(a) == find(b);
    }

직접구현하였지만 나사하나 빠진 잘못된 결과가 나와 다른사람이 작성한 코드를 이해하였다.

가장 이상적인 순서대로(비용 최소화 시킬 수 있는 간선 순서대로 적재)

queue에 적재한 간선들을 하나씩 뽑아서 부모 엣지가 다르다면 합쳐져있지 않다는 것을 의미한다.

결국 부모엣지가 하나로 합쳐지면 모두 이어졌다고 판단할 수 있는 문제

x,y,z별로 구분해서 엣지 생성은 이해했지만 그래프 합치기 구현이 꼬여서 다른사람 블로그를 참조하였다.