BFSFrom BFS에서 시작하여 다익스트라를 증명할 수 있다.모든 엣지의 weight가 1이라고 할 때 shortest path를 찾을 수 있다.  queue를 사용함src에서 시작을 해서 src를 0으로 하고, 거리를 아는 것을 다 queue에 넣음.이후, 또 인접하는걸 모두 넣는다.거리가 1인 얘들이 전부 queue에 들어가야 거리가 2인 애들이 전부 queue에 들어갈 수 있다. 1이 전부 나와야 2가 전부 들어갈 수 있다. 2,3,4도 모두 같은 방식으로 queue에 들어왔다가 나옴  찾을 수 있지만 굉장히 느리다. edge weight를 1로 만들기 위해서 dummy node를 중간 중간에 넣어 모든 edge의 weight가 1이 되도록 한다.> 그래프가 매우 커지고 느려진다.  S에 가까운 ..

Dijkstra AlgorithmVersion of DijkstraOnly Shortest Path Length for each Node 경로를 구하는 것이 아니라 길이를 구하는 것Actual Path for each Node also 패스 노드까지 구함All possible Shortest Paths for each Node 모든 shortest path를 구함 - compact하게 표현하는 방법이 필요함Alternate ExplanationsAs a Variation of BFSSelect from Nearest to Furthest계속 짧은 길을 붙여나가는 방식은 shortest path를 찾을 것 같지만, 그렇지 않다. Shortest Path기 때문에 prim 처럼 풀 수 없다.  Shortes..

Prim을 위해 만들어야할 것priority queue노드 Marking 배열그래프#include #include using namespace std;//TRI를 만들 것 노드, 노드 , wight 형태로 저장되는 것class TRI {public: int a, b, w;};//priority queueclass PQ {public: int n; TRI Arr[1000]; PQ(); //생성자 TRI Delete(); //삭제 void Insert(TRI x); //삽입 int isEmpty(); //비어있는지 확인};PQ::PQ(){ n = 0;}int PQ::isEmpty(){ return n == 0; //n에 들어있는게 없다면 0을 리턴}//prio..

Greedy Alogrithms답을 찾기 위해 선택을 반복하는 알고리즘비교적 간단한 방법으로 선택선택한 후 바꾸지 않는 알고리즘ex) selection sort -> greedy 전체에서 가장 작은걸 찾아서 새 배열의 첫번째 배열로 "선택"하여 옮김 선택하는 것은 가장 작은것을 고름 (선택을 한 쪽의 배열에서는 없어졌다고 생각)남은곳에서 또 제일 작은 것을 고르는 과정을 반복 Shortest path ideaS에서 B까지 가는 가장 짧은 길을 찾는다고 하자* S에서 A까지 가는 가장 짧은 길 등등을 찾는것과 같다. 해당 짧은 길을 찾으려면 많은 가장 짧은 길을 찾아야한다. S에서 나가는 것 중에 제일 작은 것은 5이고 C에 도착C까지 가는 5보다 짧은 길이 있는가? -> 없음 : 다른 길을 가는 순간 이..

문제 : https://www.acmicpc.net/problem/1068문제 노드를 지우면, 자식노드까지 전부 삭제하는 문제이다입력 & 출력5-1 0 0 1 11즉, 이 트리는 루트노드는 아무런 부모를 가지고 있지 않고, 1번 / 2번 노드는 0번 노드 (루트 노드)를 부모 노드로 가지고 있으며3번 /4번 노드는 1번 노드를 부모 노드로 가지고 있다.따라서 1번 노드를 지우게 되면 루트노드와 2번 노드만 남으므로최종 남는 리프노드의 개수는 1개이다.1 이 출력된다. 풀이#include using namespace std;int tree[51];int N;void deleteA(int x){ tree[x] = -2; for(int i = 0; i delateA라는 함수를 통해 어떠한 노드를 삭..