[BOJ] 백준 2887 행성 터널 / 최소 신장 트리(MST), 크루스칼

💣 문제 이해 x, y, z 좌표로 행성의 위치가 주어지고(노드), 그 행성들 사이의 거리가 가중치가 된다(간선). 행성과 행성 사이의 거리는 문제에 주어진 조건처럼 min(abs(x1-x2), abs(y1-y2), abs(z1-z2))가 된다. 이 문제는 크루스칼 알고리즘으로 풀이했다. 💭 풀이 과정 작성 언어: C++ #include #include #include #include using namespace std; class Planet { public: int x, y, z, index; Planet(int x, int y, int z, int index) { this->x = x; this->y = y; this->z = z; this->index = index; } }; class Tunne..

→2020.11.21

[BOJ] 백준 1647 도시 분할 계획 / 최소 신장 트리(MST), 크루스칼

💣 문제 이해 최소 신장 트리를 구한 뒤, 마을을 두 개로 분할할 수 있도록 도로를 제거하여 총 유지비가 최소가 되도록 하면 된다. 이 문제는 크루스칼 알고리즘으로 풀이했다. 💭 풀이 과정 작성 언어: C++ #include #include #include using namespace std; class Road { public: int start, dest, weight; Road(int start, int dest, int weight) { this->start = start; this->dest = dest; this->weight = weight; } }; const int MAX = 1001; int home_cnt, road_cnt; vector roads; vector survived_lin..

→2020.11.20

[BOJ] 백준 1922 네트워크 연결 / 최소 신장 트리(MST), 크루스칼

💣 문제 이해 컴퓨터를 노드로, 선 연결을 간선으로 보고 주어진 그래프에서 최소 신장 트리(MST)의 합을 구하는 문제였다. 틀은 바뀌었지만 1197번 최소 스패닝 트리 와 그냥 동일하게 풀리는 문제이다. 크루스칼 알고리즘/프림 알고리즘 두 가지 방법으로 풀 수 있다. 이 문제는 크루스칼 알고리즘으로 풀이했다. 💭 풀이 과정 작성 언어: C++ #include #include #include using namespace std; class Line { public: int start, dest, weight; Line(int start, int dest, int weight) { this->start = start; this->dest = dest; this->weight = weight; } }; co..

→2020.11.19