제 2회 (1주차) 모각코 결과

2주차 (2회차) - 트리에 대한 학습 및 문제 풀기

4803번: 트리 (acmicpc.net)

트리란?

그래프에서 사이클이 존재하지 않고, 각 노드의 개수가 N일 때, 간선의 개수가 N-1인 그래프를 말한다.

이런 트리의 특징으로는 계층을 표현 할 수 있고, 앞서 말한 것과 같이 DAG그래프의 한 종류이다.

앞서 모각코 2회차를 진행하기전 포인터를 이용하여, 간단하게 트리를 앞서 구현하였다.

이제 목표한 위 트리 문제를 풀어 볼 텐데, 앞선 3 문제와는 다르게 처음 구현하는 거라 꽤 힘들었다. 이제 문제를 풀이하기 위한 과정을 나열 하겠다.

1. 해당 문제의 간선은 무 방향성이다. STL 배열로 간선을 표현 할 건데, 쌍방으로 간선을 표현해주어야 한다.

2. 해당 문제를 풀다가, 하나의 노드가 소속된 그래프를 표현하고 싶어 찾다가, UNION-FIND 알고리즘을 발견하여, 공부하였다.

3. 임의의 노드에서 출발하여 BFS탐색을 시도하는데, BFS탐색이 역으로 탐색하는것을 막기 위해, 무슨 노드에서 출발했는지 값을 남겨, 역 탐색을 막도록 하였다. 이때, 이미 방문한 노드에 방문할 경우, 이 그래프를 0 과 UNION하였다.

4. 부모 노드가 0 이 아닌 모든 그래프를 찾아 COUNT후 출력하였다.

해당 문제를 풀면서 수많은 시행 착오를 거쳤는데, 결과적으로는 간선이 자기자신을 가르킬때, 이 노드를 포함한 그래프는 사이클이 있는 그래프라고 판정해야 했다.

또한, UNION 함수에서 해당 부모 노드에 다른 부모 노드를 연결해야 했는데, 해당 노드에 다른 부모 노드를 연결하여, 코드에 오류가 발생하여, 통과하지 못했다.

이렇게 무방향성 간선이 주어질 때, 트리 판정을 해보았다.

그렇게 푼 해당 소스 코드

해당 깃 허브에 있는 소스 코드는 후에, 유니온 파인드와 트리에 대한 심층적인 이해로 더짧고 빠르게 문제를 해결하는 소스 코드이다.

문제를 다 푼 뒤, 더 어려운 트리 문제를 도전하였다.

내 관점에서 해석한 UNION-FIND는 무작위의 객체 간의 연관 관계를 이어주고, 그 관계를 판정하는 알고리즘 기법이다.

모든 처음 객체는 자기자신을 연관관계로 가지는데, 다른 객체랑 연결, UNION을 하면 코드 작성자의 기준에 따라 둘 중하나의 객체가 다른 객체의 부모객체를 자신의 부모 객체의 부모로 바꾸게 된다.

Find 과정에서 부모를 찾는 과정이 진행되며, 이때 값이 현재 부모노드의 값을 찾으면서, 넣는 과정이 재귀적으로 이루어 지기 때문에, 값이 새롭게 초기화 된다.

UNION 과정에서는 FIND 과정에서 찾은 두 부모객체를 순위를 판정해 앞서말한대로 한 부모노드의 부모가 다른 부모노드가 되게 된다.

UNION-FIND는 다양한 방식으로 응용 할 수 있고, 쉬운 개념이다.

public static void union(int[] parent, int node1, int node2) {

    int n1 = find(parent, node1);
    int n2 = find(parent, node2);

    if (n1>n2)
        parent[n1] = n2;
    else
        parent[n2] = n1;
}

    public static int find (int[] parent, int node) {

    if (parent[node]==node) return node;
    return parent[node] = find(parent, parent[node]);
}