Chapter 08 : graph

08 : Graph

 

 

01 - 그래프의 표현 Edge list : A[2][N] Adjacency matrix : A[N][N] Adjacency List : ArrayList[N]
046 : 특정 거리의 도시 찾기
047 : 효율적으로 해킹하기
048 : 이분 그래프 판별하기
049 : 물의 양 구하기

 

 

02 - 유니온 파인드

union : (find값인) label이 다르다면, 하나의 label로 묶는 선언 find : label 출력, 똑같으면 value, 다르면 value = find(label(a)); checkSame : label이 같으면 true, 다르면 false 출력
050 : 집합 표현하기
051 : 여행 계획 짜기
052 : 거짓말쟁이가 되긴 싫어

 

 

 

 

 

03 - 위상 정렬

사이클이 없는 방향 그래프에서 노드 순서를 찾는 것 우선 순위와 관련 ArrayList<node>[N]을 사용 / 진입 차수 / queue를 사용 / 해당 노드가 진입하는 edge의 indegree[i]--;
053 : 줄 세우기
054 : 게임 개발하기
055 : 임계 경로 구하기

 

 

 

 

 

04 - 다익스트라

weight가 있고 값이 모두 "+" 일 때 출발 node와 모든 node 사이의 "최단거리" - 최단 거리 배열 D[N], 출발 노드 0, 나머지 = Integer.MAX_VALUE;  - D[N]에서 가장 값이 작은 노드를 고른다(출발노드) > 연결된 edge의 가중치를 업데이트 - Min(D[selected] + edge weight, D[connected]) - boolean[] visited 를 만들어 중복 처리
056 : 최단 경로 구하기
057 : 최소 비용 구하기
058 : K번째 최단 경로 찾기

 

 

 

 

 

05 - 벨만 / 포드

출발-다른노드 최단경로 - 음수 w가 있어도 edge 중심의 수행 가능 - minus Cycle 존재 여부 판단 가능	ArrayList<edge> edges > s, e, w // D[1] = 0, D[2~N] = INF 음수 사이클이 없을 때, 최단 거리 구성 에지 수는 N-1 D[s] != INF && D[s] + w < D[e]일 때, 값 대체 에지를 한번씩 다시 사용해 업데이트되는 것 체크
059 : 타임머신으로 빨리 가기	벨만-포드
060 : 세일즈맨의 고민	벨만-포드(뒤집기) + Money배열 추가

 

 

 

 

06 - 플로이드 / 워셜

061 : 가장 빠른 버스 노선 구하기	F / W
062 : 경로 찾기	F / W 변형 : i~k 경로 존재(1) && k~j (1) == i~j존재
063 : 케빈 베이컨의 6단계 법칙	F/W + 각 최단거리 모두 더한 값 비교

 

 

 

 

 

 

07 - 최소 신장 트리

 

064 : 최소 신장 트리 구하기

065 : 다리 만들기

066 : 불우 이웃 돕기