본문 바로가기
728x90

그래프탐색9

[PG/Python] 전력망을 둘로 나누기 📌 문제 https://programmers.co.kr/learn/courses/30/lessons/86971 코딩테스트 연습 - 전력망을 둘로 나누기 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr 📌 문제 접근 방법 인접리스트를 활용해서 연결된 전선 정보를 입력해준다. wires를 한 번 더 반복문을 돌리면서 전선들 중 하나를 끊는다. 이 때 끊긴 두 송전탑을 기준으로 전력망이 가진 송전탑의 개수를 bfs를 활용해서 구해준다. 두 전력망의 송전탑 수와 현재의 answer에 저장된 값을 비교하여 더 작은 값으로 answer 값을 갱신해준다. 끊긴 두.. 2021. 11. 14.
[Algorithm] 다익스트라(dijkstra) 알고리즘 최단 경로 알고리즘 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로 하나의 시작 정점에서 끝 정점까지 최단 경로 다익스트라 알고리즘 : 음의 가중치 허용x 벨만-포드 알고리즘 : 음의 가중치 허용 모든 정점들에 대한 최단 경로 플로이드 워샬 알고리즘 다익스트라(dijkstra) 알고리즘 시작 정점에서 거리가 최소인 정점을 선택해나가면서 최단 경로 구함 탐욕 기법 사용, MST의 프림 알고리즘과 유사 def dijkstra(start): distance[start] = 0 # 노드의 개수만큼 반복 for _ in range(N+1): min_idx = -1 min_value = float('inf') for i in range(N+1): if not visit.. 2021. 10. 21.
[Algorithm] 최소 신장 트리 (MST) 신장 트리 n개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 최소 신장 트리 (Minimum Spanning Tree) 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 Prim Algorithm 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식 임의 정점 하나 선택해서 시작 선택한 정점과 인접하는 정점들 중 최소 비용의 간선이 존재하는 정점 선택 모든 정점이 선택될 때 까지 반복 ''' 6 11 0 1 32 0 2 31 0 5 60 0 6 51 1 2 21 2 4 46 2 6 25 3 4 34 3 5 18 4 5 40 4 6 51 ''' def find_MST(s): key[s] = 0 # 정점.. 2021. 10. 21.
[Algorithm] 그래프 그래프 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료구조 정점의 개수 v개, 간선의 개수 e개 일 때 최대 간선의 개수 : v(v-1)/2 선형 자료구조 / 트리 자료구조로 표현하기 어려운 N : N 관계를 가지는 원소들을 표현하기에 용이 그래프 유형 무향/유향 그래프 : 방향의 유무 가중치 그래프 사이클 없는 방향 그래프 완전 그래프 : 정점들에 대해 가능한 모든 간선들을 가진 그래프 부분 그래프 : 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프 그래프 표현 # 노드, 간선의 개수 V, E = 7, 8 # 간선의 연결 (무방향) temp = [1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7] 위와 같은 입력이 들어왔을 .. 2021. 10. 20.
728x90

티스토리툴바