자료구조

Segment Tree


## Intro

우리가 자료를 저장하기 위해서는 여러가지 방법이 필요하다. 그 중에서도 연관성을 가지는 데이터를 정리하는 경우에는 선형적인 list만으로는 너무나 부족할 수도 있다. 하지만, Graph를 이용하기에도 데이터의 양이 방대해지고, 규칙이 없기 때문에 원하는 데이터를 찾는 연산에서 많은 시간을 소모하게 된다.

따라서, 보다 규칙적인 형태를 가지면서, 각 지점간의 관계를 가지고, 더 안정적인 구조를 찾기 위해서 고안된 것이 트리이다.

## Tree

트리(tree)란 그래프의 일종으로, 하나의 정점(root) 자체를 의미하거나 또 다른 독립된 (sub)트리를 directed edge(방향 간선)를 이용해서 연결한 자료구조를 말한다.

![Tree's Recursive form](/images/tree1.jpeg)

언뜻 보기에 굉장히 추상적인 표현일 수 있지만, 위와 같은 **재귀적 정의**를 기억하는 것도 많은 도움이 된다.

이를 좀 더 쉽게 설명하자면, 기본적으로 트리는 방향을 가진 간선으로 이루어진 그래프에서 다음과 같은 요소를 가지고 있을 경우를 트리라고 말한다.

1. 루트(root)라는 다른 정점을 가진다.
2. 루트를 제외한 모든 정점은 해당 정점으로 가는 간선(edge)이 단 하나이다.
3. 그렇기에 루트에서 모든 정점으로 연결되는 간선들의 경우의 수도 단 하나이다.

![Tree's Normal form](/images/tree2.jpeg)

이를 이해했다면, 앞 서 살펴보았던 재귀적 정의도 이해가 되었는지 다시 한 번 확인하고 가자.

**위와 같이 트리에서 루트에 연결된 서브 트리는 마치 하나의 독립적인 바구니라고 볼 수도 있다.** 트리에서는 연결된 subtree가 서로 독립적이기 때문에, 독립적인 바구니에 담는 규칙을 마음대로 정하여 독립적인 특징이 있는 데이터를 **분류**하기에 적절한 구조를 가지고 있다.

## 용어

- 깊이(depth) : 트리의 최대 높이를 의미한다. 대게 루트의 높이를 0으로 보기 때문에 노드가 2개라면, 깊이가 1인 걸로 본다. 하지만, 이는 구현자의 마음에 따라 다르게 구현할 수 있다.
- 부모(parent) : 특정 정점을 기준으로 자신을 가르키는 간선을 가진 정점을 말한다. 즉, 트리의 구조에서 상위에 있는 노드라고 할 수 있다.
- 자식(child) : 특정 정점을 기준으로 자신에서 출발하는 간선에 연결된 정점을 말한다. 즉, 트리의 구조에서 하위에 있는 노드라고 할 수 있다.
- 조상(ancestor) : 특정 정점을 기준으로 자신으로 오는 경로가 존재하는 정점을 말한다. 즉, 트리의 구조에서 부모에서 부터 루트까지에 경로의 모든 노드가 이에 포함된다.
- 루트(root) : 부모가 없는 최상단의 정점을 의미한다.
- 리프(leaf) : 자식이 없는 최하단의 정점들을 의미한다.
- 서브트리(subtree) : 트리의 각 정점은 해당 정점을 루트로 하는 트리라고 볼 수 있다. 이러한 본래 트리에 존재하는 내부 트리를 서브트리라고 한다.

## Binary Tree
  
모든 정점의 자식의 크기가 2 이하로 정해진 트리를 이진 트리(Binary Tree)라고 한다.

- Skewed Binary Tree  
  이진 트리에서 같은 depth에 있는 정점이 단 하나 밖에 없는 경우를 말한다. 마치 Linked List와 같은 형태이다. 이는 트리의 목적 중 하나인 분류라는 기능을 적절히 수행하지 못하는 형태이기 때문에 대게 좋지 않은 형태로 본다.

![skewed tree](/images/skewed-tree.png)

- Balanced Binary Tree  
  균형 잡힌 이진 트리로 좌우의 depth가 최대 1까지만 차이가 나는 경우를 의미한다.

![balanced tree](/images/balanced-tree.png)

- Full Binary Tree  
  정점이 가질 수 있는 자식의 수가 0 아니면 2로 제한되는 형태의 이진 트리를 의미한다. 그렇기에 기본적으로 균형 잡힌 형태의 트리가 생길 수 밖에 없다.

![full tree](/images/full-tree.png)

- Complete Binary Tree  
  균형잡힌 트리이면서 정점이 반드시 왼쪽부터 채워지는 트리를 말한다. 해당 트리의 가장 큰 특징은 이를 Array로 표현하기에 최적화되어있다는 점이다. 이는 후에 있을 **구현법** 파트에서 더 자세히 알아본다. 따라서, Complete Tree를 기억하고 가자.

![complete tree](/images/complete-tree.png)

- Perfect Binary Tree  
  Complete Tree와 가장 혼돈되는 개념이다. 이는 모든 이진 트리가 빈틈없이 꽉 채워진 경우를 말한다. 즉, leaf 노드의 자식의 갯수가 모두 0일 때이다.

![perfect tree](/images/perfect-tree.png)

## 속성

해당 속성은 정의에 의해서 파생되는 내용이다. 직접 상상해서 왜 안되는지를 생각해보자.

- 루트에 연결된 subtree 간에는 간선이 존재하지 않는다.
- Cycle이 존재하지 않기 때문에, Graph의 종류 중 하나인 DAG에 속한다.
- 정점과 정점 사이의 경로가 있다면, 해당 경로는 유일한 경로이다.
- 형제 노드로 이동할 수 있는 방법은 존재하지 않는다.

## 구현법

트리는 표현하기 위해서 대표적으로 두 가지를 사용한다. 리스트를 이용한 구현 방법과 구조체(or Class)를 이용한 구현이다.

### 1. 구조체

일반적으로 가장 널리 사용하는 방법이다. 먼저 Tree라는 구조체(or Class)를 정의한다.

```python
class Tree:
  def __init__(self, value, subtrees):
    self.root = value
    self.subtrees = subtrees
    # 필요에 따라서, 부모의 정보가 필요한 경우에는 parent를 저장할 수도 있다.
```

이진 트리에 경우에는 단 두 개의 subtree로 정해져있기 때문에 아래와 같은 형태를 빈번히 사용한다.

```python
class Tree:
  def __init__(self, value, left, right):
    self.root = value
    self.left = left
    self.right = right
```

이를 통해서 각 Tree type의 변수는 모두 루트 값과 subtree들을 포함하게 된다.

### 2. 리스트

트리의 각 정점의 유일한 특징을 이용하여 표현한다. depth와 왼쪽에서부터 몇 번째 인지를 나타내는 index를 같이 사용하면, 정점의 위치를 특정하여 표현할 수 있다.
따라서, 다음과 같은 식으로 Tree의 정점을 표현하는 것이다.

만약, 이진 트리와 같은 경우에는 아래와 같은 식으로 해당 노드가 어느 곳에 존재하는지를 찾을 수 있다.

1. $\text{tree}[2^{i} + j] = $ depth가 i이고, 왼쪽에서 j만큼 떨어진 정점이 지닌 값
2. $\text{tree}[i]$의 자식은 $\text{tree}[i \times 2]$ 또는 $\text{tree}[i \times 2 + 1]$이다.

![tree-to-list](/images/tree-to-list.jpeg)

이때 반드시 주의할 점은 시작 점은 0이 아니라 1이 되도록 해야한다는 점입니다.

이는 트리의 노드의 수가 제한되어 있는 경우에만 사용할 수 있으며, 효율적으로 사용하기 위해서는 최대한 Complete Tree형태를 갖추어야 한다. 왜냐하면, 왼쪽에서부터 데이터를 채우기 때문에 Complete Tree 형태의 구조여야지만 최대 효율을 낼 수 있는 것이다.

## Binary Search Tree

검색 트리(Search Tree)란 트리를 이용해서 검색을 쉽게하기 위해서 **일정한 규칙**에 따라서 데이터를 저장한다. 이 방식은 해당 자료를 조회하는 과정이 굉장히 단순화 될 수 있다는 장점을 가진다. 그 중에서도 Binary Search Tree는 일정한 규칙을 `데이터의 삽입 시에 현재 위치에 정점보다 데이터가 크다면 오른쪽, 작다면 왼쪽에 배치시킨다.`로 정의한 경우를 말한다. 이렇게 데이터를 저장하게 되면, 마치 이진 검색을 통해서 데이터를 찾는 것과 같은 효과를 가질 수 있다. 왜냐하면, 후에 내가 데이터를 찾을 때 현재 위치의 값을 확인하고 해당 값보다 찾고자 하는 값이 크다면 반드시 오른쪽에 있을 것이라는 확신을 가질 수 있기 때문이다. 이를 통해서, 검색 범위를 줄일 수 있기 때문에 우리가 마치 이진 검색을 하는 것처럼 데이터의 범위를 한정할 수 있다. 이게 앞에서 설명했던 트리가 가지는 분류의 기능이다. 기존의 리스트에서는 정렬을 통해서 index 번호가 순서라는 정보를 담고 있었다면, Binary Search Tree에서는 좌우 subtree가 대소 비교라는 정보를 갖고 있는 것이다.

하지만, 위에서 살펴보았다시피 유의할 점은 데이터가 좌우로 골고루 퍼져 있어야 한다는 점이다. 만약, 데이터가 좌축에만 쏠려있다면(skewed), 결국에는 분류로 얻는 이득이 없어진다. 따라서, 검색 시에는 시간 복잡도가 $O(N~\log{N})$ 이다.

### Skew 해결책

여기서는 Skew에 대한 자세한 해결책을 제시하지 않는다. 아래 키워드를 제시하였으니 이를 검색하여 찾아보길 권장한다. (후에 정리할 시간이 있다면, 정리하겠다.)

- 각 정점에 우선순위를 랜덤 값으로 지정하고, 각 subtree의 root는 해당 subtree에서의 랜덤 값의 총합을 우선순위로 가지게 하여 특정 트리가 데이터의 순서에 의해서 skew되는 현상을 막기 우히나 방법이 있다.(Treap)
- Tree의 Skew가 발생할 시에 rotation이라는 방법을 통해서 Skew를 해결 시키는 방법도 있다. (AVL Tree)
- 빨강과 검정이라는 이진 정보를 추가 활용하여 해결하는 방법도 있다. (Red Black Tree)

## Advanced Topic

아래 설명된 Tree에 대한 정보는 앞으로 차근차근 포스팅할 계획이다.

- DFS Tree
- Segment Tree
- Fenwick Tree
- Heap


Tree


## Intro

**구간 누적합**을 구하는 경우가 많이 발생한다. 하지만, 이를 저장하기 위해서 너무 많은 공간을 쓸 수는 없다. 예를 들어서 크기가 10,000인 집합에서 누적합으로 만들 수 있는 특정 수의 경우의 수를 구하고자 한다고 가정하자.

이 경우에 우리는 모든 누적합을 저장하기에는 공간이 너무 크다는 것을 알 수 있고, 이를 그렇다고 Brute Force하게 수행하기에도 시간이 충분하지 않을 수도 있다.

따라서, 우리는 효율적으로 누적합 정보를 저장할 수 있는 자료구조를 만들었다.
그것이 `Segment Tree`와 `Fenwick Tree`이다. 이들을 하나씩 살펴보도록 하자.

## Segment Tree

이전에 tree posting에서 Tree를 표현하는 방법으로 List를 소개하였다. 여기서도 그 방식을 이용해야 하니 잘 알지 못하겠다면, 한 번 보고 오도록 하자. 👉 [posting](/posts/tree)

우선 Segment Tree는 누적합을 표현하기 위한 이진 트리 형태의 자료구조이다. 이전에 트리는 데이터를 분류하기 위해 자주 사용한다고 하였는데, 이곳에서도 동일하다.

이는 트리의 leaf node가 원래 누적합을 배우고자 하는 리스트의 원소가 된다. 그리고 그 부모는 해당 원소들의 합으로 표현된다. 이렇게 하여 root는 전체 리스트의 총합이 되는 형태로 구현하는 것이다.

이러한 자료 구조를 가지게 되면 우리는 두 가지의 장점을 가질 수 있다.

1. 특정 구간에서의 누적합을 굉장히 빠르게 구할 수 있다. ($\log{N}$)
2. 업데이트 시에도 깨지지 않고, 이를 빠르게 적용할 수 있다. ($\log{N}$)

### 누적합 구하기 in segment

우선 해당 트리가 이미 만들어졌다는 가정하에서 어떻게 $\log{N}$ 만에 **누적합을 찾을 수 있는지**를 확인해보자.

이는 1번째 index b에서부터 6번째 index g까지의 합을 구하는 연산이다.

![segment tree find](/images/segment-tree-find.jpeg)

위에서 부터 탐색을 하기 위해서 다음과 같은 동작을 수행한다.

1. 내가 조회하고자 하는 범위가 해당 지점이 표현하는 범위의 밖이라면, 해당 지점은 의미없으므로, 탐색을 중지한다.
2. 조회 범위가 해당 지점을 완전 포함한다면, 해당값을 반환한다. (가장 큰 범위를 포함하는 지점에서부터 탐색하기 때문에 조회 범위에 엉뚱한 것이 섞이지 않는다.)
3. 만약, 그렇지 않다면 해당 지점에 포함된 영역을 더 추출해야 하기 때문에 하위 지점으로 이동한다.

노드 방문 횟수가 대략 $\log{N}$ 까지 감소하는 것을 볼 수 있다.

### 누적합 갱신 in segment

이제 실제로 **update를** 수행해보자.

5번째 index f에 1을 더하는 연산을 수행하는 그림이다.

![segment tree update](/images/segment-tree-update.jpeg)

위에서 부터 변동사항을 적용하기 위해서 다음과 같은 동작을 수행한다.

1. 내가 추가하고자 하는 위치가 해당 지점이 표현하는 범위의 밖이라면, 해당 지점은 의미없으므로, 탐색을 중지한다.
2. 추가하고자 하는 값을 해당 지점에 추가한다.
3. 해당 지점이 leaf 인지 확인하고, 맞다면 종료한다.
4. 그렇지 않다면, 하위 지점을 더 탐색한다.

### 구현 in segment

업데이트 시에도 복잡한 연산이 없이 바로 내려가면서, 덧셈이 필요한 구역에 더해주는 것으로 쉽게 구현이 가능하다.

```python
S = [1,2,3,4,5,6,7]
# tree의 크기는 원래 원래의 배열의 크기보다 큰 2의 제곱수 * 2 - 1이다.
# 하지만, 이를 더 쉽게 만드는 방법은 간단하게 곱하기 4하는 것이다.
tree = [0] * (len(S) * 4)

# 트리를 구성하는 함수이다.
# 루트에서부터 호출하지만, 결과는 밑에서 부터 구하면서 올라온다.
def make_seg(start=0, end=len(S) - 1, cursor=1):
  if start == end:
    tree[cursor] = S[start]
    return tree[cursor]
  mid = (start + end) // 2
  tree[cursor] = make_seg(start, mid, 2 * cursor) + \
                  make_seg(mid + 1, end, 2 * cursor + 1)
  return tree[cursor]

# 위에서 보았던 누적합을 조회하는 연산이다.
def find(left, right, cursor=1, start=0, end=len(S)-1):
  if left > end or right < start:
    return 0
  if left >= start and right <= end:
    return tree[cursor]
  mid = (start + end) // 2
  return find(left, right, cursor * 2, start, mid) \
    + find(left, right, cursor * 2 + 1, mid + 1, end)

# 위에서 보았던 누적합을 업데이트 하는 연산이다.
def update(idx, diff, cursor=1, start=0, end=len(S) - 1):
  if idx > end or idx < start:
    return
  tree[cursor] += diff
  if start == end:
    return
  mid = (start + end) // 2
  update(idx, diff, start, mid)
  update(idx, diff, mid + 1, end)

make_seg() 
print(find(1, 6)) # 28
update(3, 5)
print(find(1, 6)) # 33
```

## Fenwick Tree

segment tree와 동일하게 fenwick tree도 list를 통해서 tree를 표현한다.
또한, segment tree에서는 기존 배열의 시작점을 어디로 하던 상관없었지만, 구현 상의 편의를 위해서 기존 배열을 왼쪽에서 한 칸 밀어주는 것을 추천한다.

기본적으로 Fenwick Tree는 이진수의 특징을 활용한 연산을 통해서 합을 빠르게 찾을 수 있다. 먼저 Fenwick tree는 다음과 같은 형태로 구조화된다.

![fenwick-tree](/images/fenwick-tree.jpeg)

즉, 해당 수의 약수 중 가장 큰 2의 제곱 수만큼 자신을 포함한 하위 수의 누적합을 포함하는 방식이다. 따라서, 홀수의 경우는 자신만을 누적합으로 가지는 것을 볼 수 있다.
이렇게 구조화된 데이터는 LSB(Least Significant Bit, 이진수에서 가장 오른쪽에 있는 bit를 의미한다.)라는 특징을 이용해서 누적합과 해당 원소를 포함한 대상들을 찾기에 유용하다.

### 누적합 구하기 in Fenwick

우선 Fenwick Tree는 구간합을 반드시 맨 처음부터 특정 위치까지 구하는 연산만 수행가능하다. 따라서 구간이 처음부터가 아니라면, Fenwick Tree의 조회 연산을 두 번 수행하여 두 값을 빼서 구한다.

> 예시

1. h라는 값을 조회하는 경우  
  $$
  \begin{align}
      &= origin[8] \notag \\
      &= sum(8) - sum(7) \notag \\
      &= fenwick[8] - (fenwick[4 to 7]) \notag
  \end{align}
  $$
2. e + f + g의 구간합이 필요한 경우  
  $$
  \begin{align}
      &= origin[5to7] \notag \\
      &= sum(7) - sum(4) \notag \\
      &= (fenwick[4 to 7]) - fenwick[4] \notag
  \end{align}
  $$

여기서 `sum`을 구현하기 위해서 parameter로 들어온 값의 LSB에서 부터 1을 삭제하면서 진행하면 된다.
즉, 7이 들어왔다면, 이는 이진수로 $111_{(2)}$이고, 오른쪽에서부터 1을 발견할 때마다 해당 값을 누적합에 축적하고, 삭제하면 된다.

1. 누적합 acc를 0으로 초기화한다.
2. $111_{(2)}$는 LSB가 1이다. 따라서, 누적합에 fenwick[$111_{(2)} = 7$]를 더한다.
3. $111_{(2)}$에서 마지막 1을 지운다. (결과값은 $110_{(2)}$)
4. $110_{(2)}$는 LSB의 다음이 1이다. 따라서, 누적합에 fenwick[$110_{(2)} = 6$]를 더한다.
5. $110_{(2)}$에서 마지막 1을 지운다. (결과값은 $100_{(2)}$)
6. $100_{(2)}$는 LSB의 다다음이 1이다. 따라서, 누적합에 fenwick[$100_{(2)} = 6$]를 더한다.
7. $100_{(2)}$에서 마지막 1을 지운다. (결과값은 $000_{(2)}$)
8. 결과값이 0이므로 탐색을 종료한다.

![fenwick-tree-add](/images/fenwick-sum.jpeg)

### 누적합 갱신 in fenwick

특정 값에 누적합을 갱신하는 것 역시 간단하게 구현이 가능하다. LSB에서 가장 가까운 1에 1을 더해주는 연산을 더해가면서 업데이트를 수행해주면 된다.

1. $11_{(2)}$는 LSB가 1이다. 따라서, fenwick[$11_{(2)} = 3$]에 값을 더한다.
2. $11_{(2)}$에서 가장 오른쪽의 1을 더한다. (결과값은 $100_{(2)}$)
3. $100_{(2)}$는 LSB의 다디음이 1이다. 따라서, fenwick[$100_{(2)} = 4$]에 값을 더한다.
4. $100_{(2)}$에서 마지막 1을 더한다. (결과값은 $1000_{(2)}$)
5. $1000_{(2)}$는 LSB의 다다다음이 1이다. 따라서, 누적합에 fenwick[$1000_{(2)} = 8$]에 값을 더한다.
6. 더이상 더하는 것은 범위 밖이므로 종료한다.

![fenwick-tree-update](/images/fenwick-update.jpeg)

### 구현 in fenwick

```python
origin = [None, 1,2,3,4,5,6,7,8,9]
fenwick = [0] * len(origin)

def update(idx, val):
  while idx < len(fenwick):
    fenwick[idx] += val
    idx += (idx & -idx)

def sum(idx):
  acc = 0
  while idx > 0:
    acc += fenwick[idx]
    idx -= (idx & -idx)
  return acc

def make_fen(origin):
  for idx in range(1, len(origin)):
    update(idx, origin[idx])

make_fen(origin)
print(sum(7) - sum(4)) # 18
update(5, 5)
print(sum(7) - sum(4)) # 23
```

## Versus

둘 다 구간합을 구하기에 적합한 구조이지만 다음과 같은 차이점을 가지고 있다는 점을 명시하자. 상대적으로 활용성이 높은 Segment Tree를 사용하는 것이 대다수 좋을 수 있지만, Fenwick Tree가 가지는 크기의 장점과 코드의 구현이 쉽다는 점은 굉장한 이점이다.

|                    | Segment Tree                                      | Fenwick Tree                  |
| :----------------- | :------------------------------------------------ | :---------------------------- |
| find 시간복잡도    | $O(\log{N})$                                      | $O(\log{N})$                  |
| update 시간복잡도  | $O(\log{N})$                                      | $O(\log{N})$                  |
| 공간복잡도(사이즈) | $2^{k + 1}$($2^{k} \ge$ len(origin))              | len(origin)                   |
| 활용성             | 구간 내 합 뿐만 아니라 최대, 최소값으로 응용 가능 | **오직 구간 합에만 사용가능** |
| 구현 코드 길이     | 상대적으로 김                                     | 상대적으로 짧음               |


누적합


## Intro

Graph란 여러 개의 Vertex(정점)와 그를 잇는 Edge(간선)로 이루어진 형태의 자료 구조를 의미한다.

## 핵심 종류

- 무향 그래프: 방향이 없이 선으로 이어진 그래프
- 방향 그래프: 방향을 가진 그래프로 한 정점에서 다른 정점으로 가는 방향을 명시한 그래프
- 가중치 그래프: 각 간선이 가중치를 가지는 형태를 그래프
- 이분 그래프: 정점을 두 개의 그룹으로 나누었을 때, 각 그룹은 서로 연결되지 않은 점들로만 이루어지는 그래프
- **방향 비순환 그래프(Directed Acyclic Graph(DAG))**: 어느 정점에서 시작해도 cycle(순환)이 존재하지 않는 형태의 그래프. 이 그래프 형태에 tree(트리)도 해당되며, 이것이 특별한 이유는 선형으로 정렬하는 것이 가능하기 때문이다. ([DFS_위상정렬 참고](/post/DFS))

## Dense vs Sparse

그래프 관련 문제를 해결할 때, 반드시 고려해야 할 점은 해당 그래프가 Dense(밀도가 높은, edge가 많은)한 경우와 Sparse(희귀한, edge가 적은)한 경우를 모두 고려해주어야 한다. 이에 따라서, 시간복잡도가 굉장히 천차만별하게 나타나기 때문이다.

## 표현 방법

> **1. adjacent list(인접 리스트)**

각 정점마다 해당 정점에서 나가는 간선의 목록을 저장해서 그래프를 표현하는 법  

```python
import sys
# N = 정점의 수, M = 간선의 수
N, M = [int(i) for i in sys.stdin.readline().split()]
adj = [[] for _ in range(N)]
for _ in range(M):
  a, b = [int(i) for i in sys.stdin.readline().split()]
  adj[a].append(b)
  # 무향 그래프에서는 다음과 같이 반대 방향도 추가해주어야 한다.
  adj[b].append(a)
```

> **2. adjacent matrix(인접 행렬)**

인접 리스트 방식의 단점은 특정 두 정점이 연결 되었는지를 알기 위해서는 해당 정점과 연결된 모든 정점을 확인해야 한다. 인접 행렬에서는 이를 해결할 수 있다. 연결 여부를 직접 2차원 $V \times V$ 행렬로 나타내기 때문에 이를 바로 index 조회로 알 수 있다. **하지만,** 메모리를 더 잡아 먹을 수도 있고, 단순히 연결된 정점만 조회하는 연산일 경우에는 오히려 모든 정점을 조회해야 하기 때문에 비용이 증가할 수 있다. (Sparse한 graph일 수록 비용 증가가 크다.)  

```python
import sys
# N = 정점의 수, M = 간선의 수
N, M = [int(i) for i in sys.stdin.readline().split()]
adj = [[0 for _ in range(N)] for _ in range(N)]
for _ in range(M):
  a, b = [int(i) for i in sys.stdin.readline().split()]
  adj[a][b] += 1
  # 무향 그래프에서는 다음과 같이 반대 방향도 추가해주어야 한다.
  adj[b][a] += 1 
```
