다익스트라2 다익스트라 vs 크루스칼 비교 (java) 다익스트라 크루스칼 구현 방법 우선순위 큐 + dist(점화식) 우선순위 큐 + Union-Find 중심 정점 중심 간선 중심 시작점 출발점이 정해져 있는 경우 간선의 가중치가 가장 작은 것부터 시작한다 큐에 넣는 시점 dist가 갱신 될 때에만 그 점에서 출발하는 간선을 우선순위 큐에 넣어준다. 모든 정점을 우선순위 큐에 넣고 시작한다 용도 점과 점 사이의 거리를 구할 경우 최소 신장 트리를 그릴 때 끝 점과 점 사이의 최단 거리를 찾고 나면, 더이상 탐색하지 않는다. 목적에 따라 끝까지 그릴 수도 있다. 최소 신장 트리가 만들어 질 때까지(모든 점들이 다 이어질 때 까지) 탐색한다. 두 덩이일 경우 한 덩이만 그려지고 다른 한덩이는 그려지지 않는다(이어져 있지 않기 때문에) 간선 중심이므로 끝까지 가.. 2020. 2. 1. 백준 6118. 숨바꼭질(java)(수정) / 다익스트라(우선순위 큐) @ 다익스트라(사실 다익스트라 안 써도 풀 수 있다고 함. 가중치가 전부 1이니까 BFS로 풀어도 된다.) 다익스트라 개념 공부를 위해서 푼 문제 다익스트라 문제를 풀 때에는 1. 일반 큐 + 점화식을 사용해서 푸는 방법 2. 우선순위 큐 + boolean형 visit 을 사용해서 푸는 방법 (점화식의 기능을 우선순위 큐가 대신함) 우선순위 큐 + 점화식을 같이 써서 풀어야한다!!! 우선순위 큐를 쓰면, 우선순위 큐 자체가 Comparable로 점화식 역할까지 해 주기 때문에 점화식을 쓸 필요가 없다. 방문 체크를 하는 visit만 쓰면 된다. (처음에는 코드를 어떻게 짜야할지 감이 안와서 아래 코드를 참고했다) https://jaimemin.tistory.com/tag/%EB%8B%A4%EC%9D%B5.. 2020. 1. 7. 이전 1 다음
