본문 바로가기
카테고리 없음

Chap 4 - DFS, BFS, 백트래킹 - 자료구조 '트리'

by SayHiWorld 2024. 12. 21.

트리

 

1. 그래프 종류 중 하나인 '트리'

순환성이 없는 무방향 또는 방향 그래프

 

- 특정하지 않는 한, 어떤 노드이던지 루트가 될 수 있다. 

- 가장 바깥쪽 노드를 리프노드라고 한다.

- 노드 a에서 노드 b로 가는 방향은 반드시 존재한다.

- 노드개수는 간선개수보다 한개 더 많다. 

 

방향이 있는 트리라면, 부모->자식 관계를 나타낸 것이다. 

 

* 문제에는 주로 방향성이 있는 트리가 더 많이 나올 것이다.

 

2. 코드로 그래프를 나타내는 법

 

덱, 힙과 달리 그래프는 따로 제공되는 라이브러리가 없다. 

직접 구현을 해야한다.

 

이걸 구현하는 방법은 몇가지가 있다.

 

2-1. 인접행렬로 구현하는 방식

  0 1 2 3
0 0 1 1 1
1 0 0 1 0
2 0 0 0 0
3 0 0 1 0

 

세로에 적힌 쪽이 '출발 간선'의 정보이고,

가로에 적힌 족이 '도착 간선'의 정보이다. 

 

만약 양방향 그래프라면, 한쪽이 채워질때 반대쪽도 채워지게 될테니 대칭행렬이 된다. 

 

2-2. 인접리스트로 구현하는 방식

0 1 2 3    
1 2        
2          
3 2        

 

0과 연결된 노드들에 대한 리스트, 1과 연결된 노드들에 대한 리스트.. 이렇게 각각의 리스트를 만든다. 

 

만약 양방향 그래프라면, 0 리스트에 1 이 있다면, 1 리스트에도 0 이 있을 것이다. 

 

 

 

*문제 ) 두 가지 방법이 있다면 둘 중에 하나를 골라서 써야하는데, 어떤걸 써야할까.

 

인접행렬 vs 인접리스트 판단 기준

비교 -  인접 행렬이 인접리스트보다 훨씬 더 공간을 많이 차지함. 

이유 - 노드가 n 개면, n 제곱 만큼 무조건 쓰게됨. 연결되지 않은 노드들에 대한 정보도 '0'으로 표시해야하기 때문.

인접리스트는 간선 개수가 적으면 적을수록 메모리 차지하는게 굉장히 적어짐.

노드가 n 개이더라도, 간선 개수가 적으면 메모리 적음.

 

인접행렬의 장점은? 시간과 공간이 trade off 니까, 대신 시간 측면에서는 유리함.

임의 접근을 이용해서 검색 가능. 

 

예를 들어, 0에서 3으로 간선이 있는지 확인하는 경우를 생각해보자.

 

인접행렬이라면, G[0][3] 으로 바로 접근이 가능하다.  -> o(1)

 

인접 리스트라면, 0번 리스트에서 첫번째 요소부터 시작하여 해당 요소가 3인지 확인해보아야 한다. -> o(n)

 

결론: 시간 -> 인접 행렬 win, 공간 -> 인접 리스트 win.

 

정점 개수와 간선 개수가 최대 몇개까지 주어지는 확인.

 

대부분 둘 중 뭘쓰던 통과되는 문제가 많지만, 둘 다 쓸 줄은 알아야함.

정점이 N개일 때, 

최대 간선 개수가 많다면(N 제곱), 인접 행렬보다 인접리스트를 쓰는게 유리할 수 있음.

적다면 (2N), 인접 행렬을 쓰는게 유리할 수 있음.