시작이 반

필요 항목 PriorityQueue graph[][] dist[] ex) 양방향 Vertex = n Edge[][] = [[1, 2, 1], [2, 3, 3], [5, 2, 2], [1, 4, 2], [5, 3, 1], [5, 4, 2]] (u, v, cost) 다익스트라는 2차원 배열을 선언하여 graph[u][v] = cost 를 저장한다. (벨만포드는 edge(u, v, cost)만 보고 2중 반복문) int[][] graph = new int[n][n]; 양방향이기 때문에 graph[u][v] 와 graph[v][u] 를 둘다 채워준다. for( int[] edge... Edge ){ int u = edge[0]; int v = edge[1]; int cost = edge[2]; graph[u][..

벨만포드는 음수간선이 있을때 시작 노드에서 다른 노드까지의 최단거리를 구하는 알고리즘이다. 시간복잡도 : O(VE) Edge( [u, v, cost] .... ) dist[처음 시작 노드] = 0 나머지 INF for( i 노드 개수 V ) for( j 간선 개수 E ) 출발 노드 = Edge[j][0] -> u 도착 노드 = Edge[j][1] -> v 비용 = Edge[E][2] -> cost if ( dist[출발노드] == 무한 ) continue; if ( dist[도착노드] > dist[출발노드] + cost ) dist[도착노드] = dist[출발노드] + cost ***********중요*********** if ( i == V - 1 ) 음수 사이클 존재

경우의 수를 탐색해 나가는 도중 찾는 해가 아니면 이전 상태로 되돌아가서 다시 해를 찾는 방법이다. 주요 개념은 해를 얻을 때까지 모든 가능성을 시도한다는 점이다. 모든 가능성은 하나의 트리처럼 구성할 수 있으며, 가지 중에 해결책이 있다. 트리를 검사하기 위해 깊이 우선 탐색을 사용한다. 탐색 중에 오답을 만나면 이전 분기점으로 돌아간다. 시도해보지 않은 다른 해결 방법이 있으면 시도한다. 해가 되지 않을 것 같다면 그 아래의 탐색은 중지하고 이전 분기점으로 되돌아가는데 탐색 횟수가 줄어들게 된다. 이를 가지치기라고 한다. 즉 가지치기를 얼마나 잘하느냐에 따라서 효율성이 결정된다. 모든 트리를 탐색하게 된다면 해가 없을 것이다. 백트래킹은 기본적으로 완전탐색 카테고리에 있다. 다른 알고리즘 방법으로 해..

DFS 와 BFS 언제 사용? 보통 문제들을 보면 DFS와 BFS를 둘 다 사용하여 풀 수 있다. (모든 정점들을 탐색하는 알고리즘) BFS는 최단경로 문제, 가중치 없는 그래프 문제에 적합하다. (미로 같은 문제) DFS는 경로의 특징을 저장해야 하는 문제에 적합하다. 가중치 관리가 용이하고 탐색에 대한 제약 조건이 있는 문제 위상정렬에도 DFS를 사용한다고 한다. DFS출력값의 역순은 위상정렬의 결과와 같다. 참고 - devuna.tistory.com/32 - ssssum.tistory.com/3