기억하고싶은것들

• DFS의 개념
• DFS에 대한 간단한 코드 설명
• DFS의 장단점
• LeetCode 예시 문제 및 예시 코드

DFS는 깊이 우선 탐색이라고 불리는 알고리즘이다.

해당 알고리즘은 보통 그래프 탐색을 하는 경우에 사용된다.

그래프 탐색이란 - 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.

예를 들어, 특정 도시에서 다른 도시로 이동을 할 수 있는지 탐색하는 것이 될 수 있다.

그래프 탐색 방식 중의 하나로 DFS ( 깊이 우선 탐색)은 

그래프를 탐색 할때 , 깊이를 우선적으로 탐색하겠다는 전략이다. 

시작점부터 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하고 넘어가는 방법이다.

스택이나 재귀함수를 통해서 구현할 수 있는데 재귀 함수가 구현이 간편하기에 대부분 재귀 함수로 구현한다.

해당 설명을 코드로 표현한 간단한 의사코드를 나타내면 아래와 같을 수 있다.

void search(Node root) {
  if (root == null) return;
  
  visit(root); // 1. root 노드 방문 (방문한 노드를 표시)
  
  // 2. root 노드와 인접한 정점을 모두 방문
  for each (Node n in root.adjacent) {
    if (n.visited == false) { // 3. 방문하지 않은 정점을 찾는다.
      search(n); // 4. root 노드와 인접한 정점 정점을 시작 정점으로 DFS를 시작
    }
  }
}

DFS의 장단점은 아래와 같을 수 있다.

장점 

• 현재 경로(branch)상의 노드들만 기억하면 되므로, 저장 공간의 수요가 비교적 적음 
• 코드가 직관적이고 상대적으로 구현하기 간단하다

단점

• 재귀함수를 이용하기 때문에, 함수 호출 비용이 추가적으로 들어간다
• 재귀 깊이가 지나치게 깊어지면 stack 메모리 비용을 예측하기 어렵다
• 최단 경로를 알 수 없다 ( 단지 해당 노드를 방문할 수 있냐 없냐 만 판단할 때 쓰기 적합하다)

예시문제

1026 Maximum Difference Between Node and Ancestor ( 조상과 노드 사이의 최대 차이값 )

joomn11.tistory.com/36

1448 Count Good Nodes in Binary Tree ( 이진트리의 Good 노드 갯수 )

joomn11.tistory.com/35

1038 Binary Search Tree to Greater Sum Tree ( BST를 GreaterSumTree로 변환 )

joomn11.tistory.com/33

• Union Find , Disjoint Set 개념 
• Union Find 과정
• Union Find 코드

Union Find라는 개념을 찾으면 항상 Disjoint Set이라는 설명이 같이 나온다. 

각각의 개념에 대해서 알아보고 실제로 구현된 예제에 대해서 알아보도록 하자

Union Find ( 유니온 퐈인드) 

- 상호 배타적으로 이루어진 집합을 효율적으로 표현하기 위해 만들어진 자료구조를 표현할 때 사용하는 알고리즘

여기서 말하는 "상호 배타적으로 이루어진 집합"은 "공통 원소가 없는 부분 집합"이라고 이해하면 된다.

즉, 공통 원소가 없는 부분 집합을 효율적으로 표현하기 위해 만들어진 자료구조를 표현할 때 사용하는 알고리즘이다.

보통, 여러 개의 노드가 존재할 때 두개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 데 사용된다.

( 아직 이해가 잘 되지 않는다면, 아래 그림을 통해서 표현하는 부분을 보면 도움 될 수도 있다) 

그럼 항상 세트로 등장하는 Disjoint Set은 무엇인가

Disjoint Set ( 디스조인트 셋)

- 상호 배타적으로 이루어진 집합을 효율적으로 표현하기 위해 만들어진 자료구조

이 두 가지 정의를 보면 공통점이 있다.

"상호 배타적으로 이루어진 집합을 효율적으로 표현하기 위해 만들어진 자료구조"이다.

즉, 정리하면 Disjoint Set은 어떠한 자료구조이고, Union Find는 해당 자료구조를 표현하는 알고리즘이다.

Union Find 과정

아래 그림과 같이 여러 개의 노드가 존재한다고 해보자.

현재는 모든 노두가 서로 연결되지 않고 각자 자기 자신만을 집합의 원소로 가지고 있다.

즉, 모든 노드가 자기 자신을 가리키고 있다.

아래 표의 i는 '노드 번호', parent[i]는 '부모 노드 번호'를 의미한다 ( 자신이 어떠한 부모에 포함되어있는지를 나타냄)

이때, Union( 1, 2 ) - 1, 2 노드를 연결하게 되면

위의 그림과 같이 노드 1의 parent가 노드 2로 변경된다. 

다음으로, Union( 2, 3) - 2, 3 노드를 연결 하게 되면

다음으로, Union( 4, 5) - 4, 5 노드를 연결 하게 되면

위와 같은 Union 함수를 호출하는 동작은 '합치기' 연산을 수행한다. 

param으로 받은 노드를 연결하고 연결된 노드의 parent값을 바꾸어 주는 역할을 한다.

위에 개념에서 설명한 '공통 원소가 없는 부분 집합'은 그림에서 {1,2,3}, {4,5}에 해당한다고 이해하면 된다. 

다음으로 Find 연산은 위의 각각의 원소가 어떠한 부분 집합에 속해 있는지 찾는 과정이다. 

parentVal = Find ( i, parent)와 같이 노드가 어떠한 부분 집합에 속해있는지 반환해준다. 

만약, 위의 예시에서 Find ( 1, parent)를 수행한다면 return 값으로는 3 값이 나온다.

( 1의 부모 2 -> 2의 부모 3 -> 3의 부모 3 (자기 자신) ) 

위의 내용을 정리해 보면 

• make-set 
  • 초기화 ( parent를 자기 자신으로 지정 ) 
• Union(a, b)
  • 합치기 ( a와 b가 속한 집합을 합친다 )
• Find ( a )
  • a가 속한 집합 번호를 찾는다

Union Find 코드

    private void union(int a, int b, int[] parents) {
        int aParent = find(a, parents);
        int bParent = find(b, parents);

        if (aParent == bParent) return;
        parents[aParent] = bParent;
    }

    private int find(int node, int[] parents) {
        while(node != parents[node]) {
            node = parents[node];
        }
        return node;
    }

실행 코드 

    public static void main(String[] args) {

        int [][] edges = {{1,2}, {2,3}, {3,4}, {1,4}, {1,5}};
        int [] rst = findRedundantConnection(edges);

        System.out.println(Arrays.toString(rst));
    }
    
    public static int[] findRedundantConnection(int[][] edges) {
        int[] parents = new int[2001];

        for (int i = 0; i < parents.length; i++) { // make-set (init)
            parents[i] = i;
        }

        for (int[] edge : edges ) {
            int from = edge[0], to = edge[1];
            if (find(from, parents) == find(to, parents)){ // same parent ! 
                return edge;
            }

            union(from, to, parents);
        }
        return null;
    }