백준 - 도시 분할 계획 1647

MST 관련 문제를 찾아서 풀다가 어떤 알고리즘을 적용해야 되는지는 알겠는데 도저히 사이클의 여부를 확인할 수 있는 방법을 알지 못해서 많이 헤맸다. 그래서 기록을 남기기 위해 적게 되었다.

 

백준 - 도시 분할 계획

 

 

블로그 목차

 

1. 원리

2. 코드

 

 

원리

 

- 원리는 어떤 노드의 부모가 누군지를 기록하는 배열을 이용하는 것이다.

- 예를 들어, (2, 3) 간선을 추가하는 과정이라면, 2의 부모 노드가 누구인지 3의 부모 노드가 누구인지를 찾아서 비교한다.

- 만약 다르다면 서로 연결되어 있는 것이 아니기 때문에 (2, 3) 간선을 추가하면 되고, 부모 노드가 같다면 서로는 이미 연결되어 있기 때문에 간선을 추가할 수 없다.

- 아! 위의 아이디어가 크루스칼 알고리즘에서 간선을 하나씩 추가할 때, 사이클의 여부를 확인하는 아이디어라면, 문제에 대한 아이디어는 다음과 같다.

- 주어진 간선들을 가지고 MST를 만들고, MST에서 가장 비용이 높은 간선 하나를 자르면 서브 그래프가 두 개가 생긴다(이것이 왜 그런지는 MST의 특성을 알면 바로 알 수 있다).

- 나같은 경우에는 컴포넌트 간의 의존 관계 그래프를 MST로 만들고 가중치가 높은 간선을 하나씩 잘라나가면서 그래프를 분할하는 형태로 마이크로서비스를 식별하는 기존 기법을 알고 있기 때문에 아이디어를 떠올리기 쉬웠던 것 같다.

- 서브 그래프가 두 개가 생기면 마을이 두 개로 분할되었기 때문에 이제 두 마을에 남아있는 간선들의 비용을 다 합치면  문제의 정답이 된다.

 

문제 풀이!!

 

문제에 기술되어 있는 샘플 예제를 그대로 활용해서 크루스칼로 풀어보자.

먼저, 에지들을 비용이 적은 순서대로 정렬을 한다. 그래야 하나씩 추가하면서 MST를 만들 수 있기 때문이다.

그러고 나서 아래와 같이 노드의 부모 노드를 기록해둔다. 초기에는 자기 자신이다.

1	2	3	4	5	6	7
1	2	3	4	5	6	7

 

1) (3, 2) 에지를 추가한다.

3의 부모는 3이고, 2의 부모는 2다. 따라서 부모 노드가 서로 다르기 때문에 해당 간선은 추가할 수 있다.

따라서 간선을 추가한다. 그러면 2의 부모는 3이 된다.

1	2	3	4	5	6	7
1	3	3	4	5	6	7

 

2) (6, 4) 에지를 추가한다.

6의 부모와 4의 부모가 서로 다르기 때문에 간선을 추가한다. 아래와 같이 배열이 변경된다.

1	2	3	4	5	6	7
1	3	3	6	5	6	7

 

3) (1, 3) 에지를 추가한다.

1의 부모와 3의 부모가 서로 다르기 때문에 간선을 추가할 수 있다. 아래와 같이 배열이 변경된다.

1	2	3	4	5	6	7
1	3	1	6	5	6	7

 

 

4) (2, 5) 에지를 추가한다.

2의 부모와 5의 부모가 서로 다르기 때문에 간선을 추가할 수 있다.

이때, 2의 부모를 탐색하는 과정에서 2 -> 3 -> 1 과 같이 거슬러 올라갈텐데 나중에도 계속 이런 과정을 반복하는 것은 비효율적이므로 2의 부모를 3이 아니라 최상위 부모인 1로 변경한다.

또한, 2의 최상위 부모가 1이기 때문에 5도 마찬가지로 부모 노드가 1로 변경된다.

 

아, 그리고 서브 그래프끼리 합쳐지는 상황이 있기 때문에 (x, y) 에지가 주어질 때, 간선이 추가될 수 있다면 y의 부모를 x로 바꾸는 것이 아니다!

정확하게는 y의 최상위 부모를 x의 최상위 부모로 바꾸는 것이다.

그 이유는 아래에서 설명할 수 있다.

1) 만약 위 상태에서 0이라는 노드가 있다고 가정하고, (0, 2) 에지가 추가된다고 해보자

2) 2의 부모와 0의 부모가 달라 에지가 실제로 추가된다면, 2의 부모 노드를 0으로 바꾸면 될까?

3) 그러면 바로 서브 그래프가 되버린다.

1	2	3	4	5	6	7
1	0	1	6	1	6	7

- 0과 2로 연결된 그래프와, 1, 3, 5가 연결된 그래프, 4, 6이 연결된 그래프, 그리고 7만 있는 그래프가 생긴다.

- 따라서, 이럴 때는 2의 최상위 부모 노드의 부모 노드 값을 0의 부모 노드 값으로 바꿔야 한다.

- 2의 최상위 부모 노드 값이 1이기 때문에 1의 부모 노드 값을 0의 부모 노드 값인 0으로 바꾼다.

1	2	3	4	5	6	7
0	1	1	6	1	6	7

- 이제 0, 1, 2, 3, 5로 연결된 그래프가 제대로 생성된 것을 볼 수 있다.

 

다시 4)의 과정으로 돌아오면 아래와 같이 배열이 변경된다.

1	2	3	4	5	6	7
1	1	1	6	1	6	7

 

 

5) (1, 6) 에지가 추가된다.

1의 부모와 6의 부모가 다르기 때문에 추가될 수 있다. 아래와 같이 배열이 바뀐다.

1	2	3	4	5	6	7
1	1	1	6	1	1	7

 

6) (1, 2) 에지가 추가된다.

그런데 1의 부모와 2의 부모가 같다. 즉, 이미 연결되어 있다. 그러므로 이 간선은 추가하지 않는다.

 

7) (6, 5), (4, 5) 에지는 부모가 다 같기 때문에 추가되지 않는다.

 

8) (3, 4) 에지가 추가된다.

3의 최상위 부모는 1, 4의 최상위 부모는 6->1로 결국 1이기 때문에 같다. 따라서 추가되지 않는다.

 

9) (6, 7) 에지가 추가된다.

6의 부모와 7의 부모가 서로 다르다. 추가된다. 배열은 아래와 같이 변경된다.

1	2	3	4	5	6	7
1	1	1	1	1	1	1

 

10) 나머지 간선들은 추가되지 않는다.

 

자 이제 MST를 만들었다.

엥? 정답은 그러면 언제 계산되는가?

 

바로 에지가 추가될 때마다 비용을 계속 더한다. 그러고 나서 가장 마지막에 추가된 비용은 제외시키면 최초의 알고리즘 아이디어와 일치하게 된다. 아래는 코드이다.

 

아래의 코드에서 주석이 쳐진 부분은 굳이 추가하지 않아도 된다. 이것은 에지를 추가할 때, 부모 노드가 될 수 있는 노드의 규칙을 정해놓는 것인데, 이렇게 하게 되면 일종의 규칙이 생기기 때문에 최상위 부모가 계속 바뀌는 것이 덜 일어난다.

코드

import java.util.*;
import java.io.*;
public class Main {

    int N;
    int M;
    int[][] edges;
    int[] parent;

    public int findParent(int node) {
        if (parent[node] != node) {
            parent[node] = findParent(parent[node]);
        }
        return parent[node];
    }

    public void solve() {
        parent = new int[N];
        for (int i = 0; i < N; i++)
            parent[i] = i;

        ArrayList<Integer> w = new ArrayList<>();

        for (int i = 0; i < edges.length; i++) {
            int x = edges[i][0];
            int y = edges[i][1];
            int cost = edges[i][2];

            int x_parent = findParent(x);
            int y_parent = findParent(y);

            if (x_parent != y_parent) {
                w.add(cost);
//                if (x_parent < y_parent)
//                    parent[y_parent] = x_parent;
//                else
//                    parent[x_parent] = y_parent;
                parent[y_parent] = x_parent;
            }
        }

        int answer = 0;
        for (int i = 0; i < w.size()-1; i++) {
            answer += w.get(i);
        }
        System.out.println(answer);
    }

    public void input() throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        edges = new int[M][3];

        int x;
        int y;
        int cost;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(bf.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            cost = Integer.parseInt(st.nextToken());

            edges[i][0] = x - 1;
            edges[i][1] = y - 1;
            edges[i][2] = cost;
        }

        Arrays.sort(edges, ((o1, o2) -> {
            return o1[2] - o2[2];
        }));
    }

    public void solution() throws IOException {
        input();
        solve();
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}

 

MST가 생각보다 어려웠다. 전공 수업에서 프림 알고리즘과 함께 문제를 막 풀기도 했었는데, 기록을 안해두니 머리에 오랫동안 남지 않았던 것 같다. 특히, 내가 4) 과정에서 적어둔 내용은 최초에 크루스칼 알고리즘을 구현했을 때 했던 실수이다. 왜 자꾸 정답이 틀린지 1시간~2시간 정도 코드를 계속 살펴보다가 알아차릴 수 있었다. ㅠㅠ

추천글

https://www.acmicpc.net/problem/1647