자바 알고리즘 Graph 추가 이해하기

✔ Graph

-  1: N / N:N 

- 인접리스트 , 인접행렬로 접근

- 가중치가 있는 것(값이 있는 경우) 없는것

 

• 인접행렬 그래프 표현

- 가중치가 없는 경우 True 1 False 0

  가중치가 있는 경우 True (가중치 값) False 0

- 노드가 N개 있을 때 행렬은 N * N (노드 * 인접정보)

 

NODE수	인접행렬	배열크기	메모리	수행 횟수
100	100 * 100	10,000	10K ,4K	10,000
1000	1000 * 1000	1,000,000	1M, 4M	1,000,000
10000	10000 * 10000	100,000,000	100M, 400M	1억!!!!

 

노드수가 10,000이라면 메모리 초과 시간 초과로 인접행렬로 구현하기 어렵다!!!
=> 인접 리스트로 사용 해야 한다 / 인접 리스트 수행 속도 Node * Link

 

- 링크정보면서 단반향 X

from ->to / to->from 둘다 생각!

 

문제 미로탐색

경계, 방문체크, 이동 여부 0 이동X , 1 이동 o

첫 시작도 카운팅 하니까 1부터 헤야 하는 구만!!

 

(1,1) 패딩을 해야해? 아닝 (0,0) (n-1,m-1)로 생각

최소 칸수 = 최소 비용 = 최소 거리

가중치 없음!! => BFS!!!!!!! => 시작위치에서 한번씩만 이동하니깐!!

• 인접리스트

: 해당 노드와 연결되어있는 노드들을 리스트로 쭉 붙이는 방식

출처: born2bedeveloper.tistory

행렬의 경우

: 두 정점이 연결되있는지를 확인하는 방법으로 활용

=> graph[x][y]의 값을 바로 확인해서  유무를 판단

=> 정점이 N개인 경우, 행렬을 만들기 위해선 N * N만큼의 공간이 필요

 

리스트의 경우

: 실제 연결된 노드들만 리스트 원소에 담겨있음

=> 공간 복잡도가 N(간선)

=> 다만, 두 정점 x, y가 연결되있는지 알고 싶다면

노드x 리스트로 들어가 원소 y가 있는지 처음부터 쭉 탐색해야 하므로 행렬보다 더 많은 시간이 소요