Computer Science/Computer Algorithms18 [Computer Algorithms] Disjoint-Set : Union-Find (서로소 집합) 1. 각 노드의 부모를 자기 자신으로 초기 설정한다.2. Find는 한 set에 있는 노드들의 부모 노드로의 경로를 압축하여 노드들이 공통된 하나의 부모 노드를 가리키게 하고, 이를 return하게 한다.3. Union는 두 노드의 부모 노드를 비교하여 큰 수의 부모 노드가 작은 수의 부모 노드의 자식 노드가 되게 한다. #include #include #include using namespace std;int V, E;int parent[101];int find_parent(int x){ if (parent[x] != x) parent[x] = find_parent(parent[x]); return parent[x];}void union_parent(int x, int y){ .. 2024. 6. 28. [Computer Algorithms] Floyd-Warshall Algorithm (플로이드-워셜 알고리즘) 1. 행렬의 원소를 무한대로 설정한다.2. 자기자신을 향하는 것을 의미하는 주대각원소들은 0으로 설정한다.3. 간선을 입력 받는다.4. a에서 b로 향하는 최단 거리는 a에서 k를 거쳐 b로 가는 경로중 가장 짧은 것을 찾아 설정한다.#include #include #include #define endl '\n'#define INF 1000000000 // 1e9using namespace std;int N, M;int graph[101][101];void input(){ cin >> N >> M; fill(&graph[0][0], &graph[100][101], INF); for (int i = 1; i > from >> to >> weight; graph[from][to].. 2024. 6. 27. [Computer Algorithms] Dijkstra's Algorithm (데이크스트라의 알고리즘) 1. 출발 노드를 설정한다.2. 최단 거리 테이블을 무한대로 초기화한다. (출발 노드는 0으로 초기화)3. 간선을 출발지, 도착지, 가중치 순서로 입력한다4. 출발 노드의 거리와 노드 번호를 우선순위 큐에 넣는다.5. 우선순위 큐의 최상위 노드를 선택한다. (최단 거리가 가장 짧은 노드)6. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블을 갱신한다.7. 갱신된 노드의 거리와 노드 번호를 우선순위 큐에 넣는다.8. 우선순위 큐가 Empty한 상태가 될 때 까지 5 ~ 7을 반복한다.#include #include #include #define endl '\n'using namespace std;int N, M; .. 2024. 6. 27. 이전 1 2 다음