말감로그

다익스트라 알고리즘과 프림 알고리즘에 대한 차이가 궁금해져 찾아봤다. 다익스트라와 프림은 모두 그래프 알고리즘 중 하나로, 그래프에서 최소 비용의 경로 또는 트리를 찾는 데 사용된다. 그러나 두 알고리즘은 목적과 적용되는 상황에서 차이가 있다. 1. 목적 - 다익스트라 알고리즘 : 주어진 출발 노드에서 다른 모든 노드까지의 최단 경로를 찾는 것이 목적이다. 주로 하나의 출발점에서 다른 모든 지점까지의 최단 경로를 찾는 데 사용된다. - 프림 알고리즘 : 주어진 그래프에서 최소 신장 트리를 찾는 것이 목적이다. 주로 그래프에서 모든 노드를 연결하는 최소 비용의 트리를 찾는 데 사용된다. 더보기 최소 신장 트리 그래프에서 모든 노드를 가장 적은 비용으로 연결하는 트리. 그래프의 모든 노드를 포함하고, 사이클..

1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개..

그래프 탐색의 목적은 모든 정점을 한 번씩 방문 하는 것이다. 어떻게 방문할 것이냐에 따라 DFS와 BFS로 나뉜다. DFS - 깊이 우선 탐색 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식. 모든 노드를 방문하고자 하는 경우에 이 방법을 사용 그래프의 구조를 파악하는데 유용 BFS에 비해 간단하지만 검색 속도가 느림 스택 또는 재귀함수로 구현 활용: 미로 찾기 DFS 구현 방법 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노..