코딩성장스토리

오랜만에 문제를 풀다가 헷갈리는 부분들이 있어서 정리를 해본다.. 최소 스패팅 트리 모든 노드에서 가중치 합이 가장 작은 트리를 만드는 것 크루스칼 vs 프림 크루스칼 알고리즘 간선의 길이가 짧은 것 부터 시작해서 사이클이 생기지 않게 간선을 추가하는 방식 프림 알고리즘 한 시작 노드를 정한 후에 노드에 연결된 간선 중 최소 값을 선택하여 확장해나가는 방식 크루스칼 알고리즘 구현 // 유니온 파인트도 사이클 체크 int findparent(int x){ if(x==findparent(parent[x])){ return x; }else{ return parent[x]=findparent(parent[x]); } } void uni(int x,int y){ x=findparent(x); y=findparen..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 이 문제는 다익스트라 문제이다. 하지만 ! 기존에 하던 다익스트라 방식으로는 시간초과가 난다.. 그래서 왜지... 라는 의구심을 가지고 생각을 해봤다.. 아래가 시간초과가 난 코드다 . 이 코드의 잘못된 점을 찾아보면 방문된 점의 처리가 제대로 안되어 있다는 것이다. 인접한 점의 노드의 간선들을 모두 우선순위 큐에 넣는 방식이다. 이때 이미 방문했던 노드들은 굳이..