[Algorithm]

🦕 treeDFS

🍀 문제 풀이

🌲 회고

날이 갈수록 심화되는 알고리즘..턱없이 부족한 자료구조분석실력 및 방대한 양...완전 길을 잃어버린 느낌..이거 난이도 너무 심한거 아닌가요? 그래도 정규수업에 있으니 따라갈 수 밖에 없는 상황인데 부랴부랴 구글링 하고 트리구조 부터 DFS 훑어보았지만 도대체 무슨 소리 하는 건가요? 하는 느낌을 받는 와중에..논문이 나왔다는 따끈한 소식을 듣고 참고하였다. 1달 정도 남았는데 앞으로 걱정이 태산..잘할 수 있을지 의문의 1패를 벌써 맞은 느낌이라고나 할까? 도망가면 붙잡으로 갈꺼다...가지말라고 하시는 분들 보면 오늘도 나는 묵묵히 내 갈길 걸어가본다...

🌳 알고 넘어가기

🌓 트리(Tree)의 개념

트리는 노드로 이루어진 자료 구조

1).트리는 하나의 루트 노드를 갖는다.
2).루트 노드는 0개 이상의 자식 노드를 갖고 있다.
3). 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.

• 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성되어 있다.
  • 트리에는 사이클(cycle)이 존재할 수 없다.
  • 노드들은 특정 순서로 나열될 수도 있고 그럴 수 없을 수도 있다.
  • 각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있다.
    - 각 노드는 어떤 자료형으로도 표현 가능하다.

class Node {
  public String name;
  public Node[] children;
}

• 비선형 자료구조로 계층적 관계를 표현한다. Ex) 디렉터리 구조, 조직도

1. 그래프의 한 종류

• 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph)
• 또는 DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류 이다.

🌱Tree와 관련된 용어

• 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
• 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
• 내부(internal) 노드: 단말 노드가 아닌 노드
• 간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)
• 형제(sibling): 같은 부모를 가지는 노드
• 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
• 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
• 노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
• 트리의 차수(degree of tree): 트리의 최대 차수
• 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

🌿트리(Tree)의 특징

• 그래프의 한 종류이다. ‘최소 연결 트리’ 라고도 불린다.
• 트리는 계층 모델 이다.
• 트리는 DAG(Directed Acyclic Graphs, 방향성이 있는 비순환 그래프)의 한 종류이다.
  - loop나 circuit이 없다. 당연히 self-loop도 없다.
  - 즉, 사이클이 없다.
• 노드가 N개인 트리는 항상 N-1개의 간선(edge)을 가진다.
  - 즉, 간선은 항상 (정점의 개수 - 1) 만큼을 가진다.
• 루트에서 어떤 노드로 가는 경로는 유일하다.
  - 임의의 두 노드 간의 경로도 유일하다. 즉, 두 개의 정점 사이에 반드시 1개의 경로만을 가진다.
• 한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다.
  - 부모-자식 관계이므로 흐름은 top-bottom 아니면 bottom-top으로 이루어진다.
• 순회는 Pre-order, In-order 아니면 Post-order로 이루어진다. 이 3가지 모두 DFS/BFS 안에 있다.
• 트리는 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등이 있다.

☘️트리(Tree)의 종류

이진 트리(Binary Tree)

트리를 구성하는 노드의 branch개수는 0개, 1개, 2개, 3개, ... 등 여러 개가 될수 있지만, 이진트리는 다르다. 이진트리는 모든 노드가 최대 2개의 서브트리르 가지고 있는 트리고, 서브트리 또한 모두 이진 트리이다. 즉 branch가 최대 2개인 노드만 구성되는 트리라는 뜻이다.
간단하게 정리하자면

• 부모 노드보다 왼쪽 자식의 노드가 작다
• 부모 노드보다 오른쪽 자식의 노드가 크다
• 같은 데이터 값을 가지는 노드는 없다. (데이터 중복 X)

🍀트리(Tree)의 순회

트리 순회란, 트리자료구조에 포함된 노드들을 특정한 방법으로 한 번씩 방문하는 방법이다.
이를 통해서 정보를 시각적으로 확인할 수 있다. 바로 위에 있는 이진트리의 이미지에 노드부터 A,B,C로 예로 들어본다면,

• 전위 순회(Pre-order traversal) : 노드, 왼쪽자신, 오른쪽 자신 순서로 방문하는 순회 방법 A -> B -> C
• 중위 순회(In-order traversal) : 왼쪽 자식, 노드, 오른쪽 자식 순서로 방문하는 순회 방법 B -> A -> C
• 후위 순회 (Post-order traverl) : 왼쪽 자식, 오른쪽 자식, 노드 순서로 방문하는 순회 방법 B -> C -> A

🍀트리(Tree)의 구현 방법

기본적으로 트리는 그래프의 한 종류이므로 그래프의 구현 방법(인접 리스트 또는 인접 배열)으로 구현할 수 있다.

인접 배열 이용

1. 1차원 배열에 자신의 부모 노드만 저장하는 방법
   트리는 부모 노드를 0개 또는 1개를 가지기 때문
   부모 노드를 0개: 루트 노드
2. 이진 트리의 경우, 2차원 배열에 자식 노드를 저장하는 방법
   이진 트리는 각 노드가 최대 두 개의 자식을 갖는 트리이기 때문
   Ex) A[i][0]: 왼쪽 자식 노드, A[i][1]: 오른쪽 자식 노드

인접 리스트 이용

1. 가중치가 없는 트리의 경우
   ArrayList< ArrayList > list = new ArrayList<>();
2. 가중치가 있는 트리의 경우
   1) class Node { int num, dist; // 노드 번호, 거리 } 정의
   2) ArrayList[] list = new ArrayList[정점의 수 + 1];

그래프(Graph)

• 그래프(graph)란 사물을 정점(vertex)과 간선(edge)으로 나타내기 위한 도구다. • 그래프는두가지방식으로구현할수있다.

그래프 탐색
하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것
Ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지
https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

🌱깊이 우선 탐색 (DFS, Depth First Search)

루트 노드 혹은 다른 임의의 노드에서 시작해서 다음 분기(branch) 로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법. 즉, 넓게 탐색하기 전에 깊게 탐색하는 방법이다.

• 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
• 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.
• 사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.
• 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
• 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.

🌱 깊이 우선 탐색(DFS)의 특징

• 자기 자신을 호출하는 순환 알고리즘의 형태 를 가지고 있다.
• 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
• 이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 - 검사 해야 한다는 것이다.
  이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.

🌱 깊이 우선 탐색(DFS)의 과정

1.a 노드(시작 노드)를 방문한다.

• 방문한 노드는 방문했다고 표시한다.

2. a와 인접한 노드들을 차례로 순회한다.

• a와 인접한 노드가 없다면 종료한다.

3. a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문해야 한다.

• b를 시작 정점으로 DFS를 다시 시작하여 b의 이웃 노드들을 방문한다.

4. b의 분기를 전부 완벽하게 탐색했다면 다시 a에 인접한 정점들 중에서 아직 방문이 안 된 정점을 찾는다.

• 즉, b의 분기를 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드를 방문할 수 있다는 뜻이다.
• 아직 방문이 안 된 정점이 없으면 종료한다.
• 있으면 다시 그 정점을 시작 정점으로 DFS를 시작한다

🌱 깊이 우선 탐색(DFS)의 구현

구현 방법 2가지
1. 순환 호출 이용
2. 명시적인 스택 사용
명시적인 스택을 사용하여 방문한 정점들을 스택에 저장하였다가 다시 꺼내어 작업한다.
순환 호출을 이용한 DFS 의사코드(pseudocode)

🌱 깊이 우선 탐색(DFS)의 시간 복잡도

1. DFS는 그래프(정점의 수: N, 간선의 수: E)의 모든 간선을 조회한다.

• 인접 리스트로 표현된 그래프: O(N+E)
• 인접 행렬로 표현된 그래프: O(N^2)

2. 즉, 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph) 의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.