Algorithms과 자료구조/그래프(vertex, edge, node, arc), BFS, DFS,
-
최단 경로 문제_다익스트라, 플로이드 와샬 알고리즘Algorithms과 자료구조/그래프(vertex, edge, node, arc), BFS, DFS, 2021. 11. 25. 19:39
다익스트라 알고리즘 하나의 노드로부터 다른 노드까지의 최단경로 탐색 알고리즘으로 O(v^2)의 시간복잡도를 가졌다. 우선순위큐(힙트리)방식을 이용하면 O((V+E)logV) (v = 노드 수, E 간선수)의 시간복잡도를 가지게 된다. 조건 그래프 방향의 유무는 상관없으나 간선들중 가중치가 음수이면 사용이 불가하다. 현실세계에서도 음수의 가중치가 존재하지 않으므로 GPS소프트웨어 등에서 가장 많이 사용된다고 한다. (음의 가중치를 가지는 간선이 있으면서 가중치 합이 음인 사이클이 존재하지 않는다면 벨만포드 알고리즘을 사용 가능하다.) 작동원리 출발노드설정 출발노드기준 인접노드까지의 가중치 저장 연결되지 않은 노드 무한대 방문하지 않은 노드중 가장 비용이 적은 노드를 선택 해당 노드를 거쳐 다음 인접노드로 ..
-
위상정렬_백준 1948 임계경로Algorithms과 자료구조/그래프(vertex, edge, node, arc), BFS, DFS, 2021. 11. 24. 21:29
문제 더보기 문제 월드 나라는 모든 도로가 일방통행인 도로이고 사이클이 없다. 무수히 많은 사람들이 월드 나라의 지도를 그리기 위해서, 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색한다고 한다. 지도를 그리는 사람들은 지도를 그리는 일을 다 마치고 도착 도시에서 모두 다 만나기로 하였다. 그렇다고 하였을 때 이들이 만나는 시간은 출발 도시로부터 출발한 후 최소 몇 시간 후에 만날 수 있는가? 즉, 마지막에 도착하는 사람까지 도착을 하는 시간을 의미한다. 어떤 사람은 이 시간에 만나기 위하여 1분도 쉬지 않고 달려야 한다. 이런 사람들이 지나는 도로의 수를 카운트하여라. 출발 도시는 들어오는 도로가 0개이고, 도착 도시는 나가는 도로가 0개이다. 입력 첫째 줄에 도시의 개수 n(..
-
위상정렬_백준 1432 그래프수정_파이썬Algorithms과 자료구조/그래프(vertex, edge, node, arc), BFS, DFS, 2021. 11. 24. 15:01
백준 1432 그래프 수정 더보기 문제 N개의 정점이 있는 그래프가 주어지면, 다음과 같은 방법에 의해서 정점의 번호를 다시 매기고 싶다. 모든 그래프의 번호는 1보다 크거나 같고 N보다 작거나 같은 번호를 가져야 한다. 만약 V1에서 V2로 연결된 간선이 있다면, V2의 번호는 V1보다 커야 한다. 위와 같은 조건을 이용해서 그래프의 번호를 다시 매긴 후에, 1번 정점의 새로 고친 번호를 M1, 2번 정점의 새로 고친 번호를 M2, ..., N번 정점의 새로 고친 번호를 MN이라고 하면, N개의 수열이 만들어진다. 이 수열을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 인접행렬 형식으로 입력이 주어진다. 0은 연결되지 않았음을 의미하고, 1은 ..
-
위상정렬(topological sorting)_백준 2252 줄세우기_파이썬Algorithms과 자료구조/그래프(vertex, edge, node, arc), BFS, DFS, 2021. 11. 23. 22:25
위상정렬 위상정렬이란 위 이미지와 같이 방향성을 가진 그래의 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 순서가 정해진 작업을 차례로 수행할때 그 순서를 결정해 주기위해 사용되는 알고리즘으로 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상정렬을 이용할 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 사이클이 존재하지 않아야 한다. 즉 위상정렬을 위한 그래프는 Directed Acyclic Graph여야 한다. 위상 정렬에서는 답이 여러개일 수 있다. 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상의 경우 여러답이 존재한다. 진입차수, 진출차수 진입차수(Indegree): 특정 노드로 들어오는 간선의 개수 진출차수(outdegree): 특정 노드에서 나가는 간선의 ..
-
최소 스패닝 트리_크루스칼,프림 알고리즘Algorithms과 자료구조/그래프(vertex, edge, node, arc), BFS, DFS, 2021. 11. 22. 17:54
최소 스패닝 트리? 스패닝 트리 n개의 정점(노드)를 가지는 그래프의 최소 간선의 수는 n-1개이고 n-1개의 간선으로 연결되어 있으면 트리형태과 되며 이것은 스패닝 트리가 된다. 즉 그래프의 일부 간선을 선택해서 만든트리 MST(최소 스패닝 트리) 스패닝 트리중에서 사용된 간선들에 가중치가 있을경우 이 간선의 합이 최소인 트리이다. 최소 스패닝 트리는 단순히 가장 가중치가 적은 간선들을 사용한다고 해서 얻어지는것이 아니다. MST특징은 아래와 같다. 간선의 가중치 합이 최소여야한다. n개의 정점을 가지는 그래프에 대하여 반드시(n-1)개의 간선만을 사용한다. 사이클이 포함되어서는 안된다. MST를 구현 알고리즘 크루스칼(KrusKal)알고리즘 프림(Prim)알고리즘 1. 크루스칼 알고리즘 MST(Min..
-
트리구조_백준 1991 트리순회 파이썬Algorithms과 자료구조/그래프(vertex, edge, node, arc), BFS, DFS, 2021. 11. 19. 10:31
백준 1991 트리순회 import sys input = sys.stdin.readline n = int(input()) Tree = {} for i in range(n): data, left_node, right_node = input().split() if left_node == '.': left_node = None if right_node == '.': right_node = None Tree[data] = [data, left_node, right_node] # 전위순회 def pre_order(data: str): print(Tree[data][0], end='') if Tree[data][1] != None: pre_order(Tree[data][1]) if Tree[data][2] != N..