glowing713
Frontend-Deep-Dive
glowing713
์ „์ฒด ๋ฐฉ๋ฌธ์ž
์˜ค๋Š˜
์–ด์ œ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (97)
    • Languages (11)
      • JavaScript ๐Ÿ’› (3)
      • Python ๐Ÿ (4)
      • Java โ˜•๏ธ (3)
      • Swift ๐Ÿงก (1)
    • Computer_Science (1)
      • Computer_Network ๐Ÿ•ธ (1)
    • Web_Frontend (4)
      • Vue.js (1)
    • Problem_Solving (76)
    • Server (1)
      • Spring ๐Ÿ€ (1)
    • AI (2)
      • NLP ๐Ÿ—ฃ (1)
      • AI_Math โž— (1)
    • ๊ฐœ๋ฐœํ™˜๊ฒฝ ๊พธ๋ฏธ๊ธฐ โœŒ (1)
    • ์ƒ๊ฐ์ •๋ฆฌ โœ๐Ÿป (1)

๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

  • ๐Ÿง‘๐Ÿปโ€๐Ÿ’ปGithub

๊ณต์ง€์‚ฌํ•ญ

์ธ๊ธฐ ๊ธ€

ํƒœ๊ทธ

  • binary search
  • ps
  • ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค
  • BOJ
  • ์™„์ „ํƒ์ƒ‰
  • Java
  • boostcampaitech
  • Stack
  • DP
  • mst
  • 2019 ์นด์นด์˜ค ๊ฐœ๋ฐœ์ž ๊ฒจ์šธ ์ธํ„ด์‹ญ
  • Algorithm
  • ์นด์นด์˜ค ๊ธฐ์ถœ
  • Python
  • Baekjoon
  • brute-force
  • c++
  • bfs
  • ์ด๋ถ„ํƒ์ƒ‰
  • ๋™์ ๊ณ„ํš๋ฒ•

์ตœ๊ทผ ๋Œ“๊ธ€

์ตœ๊ทผ ๊ธ€

ํ‹ฐ์Šคํ† ๋ฆฌ

hELLO ยท Designed By ์ •์ƒ์šฐ.
glowing713

Frontend-Deep-Dive

[BOJ] ๋ฐฑ์ค€ 1647 ๋„์‹œ ๋ถ„ํ•  ๊ณ„ํš / ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ(MST), ํฌ๋ฃจ์Šค์นผ
Problem_Solving

[BOJ] ๋ฐฑ์ค€ 1647 ๋„์‹œ ๋ถ„ํ•  ๊ณ„ํš / ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ(MST), ํฌ๋ฃจ์Šค์นผ

2020. 11. 20. 15:19

์ด๋ฏธ์ง€๋ฅผ ํด๋ฆญํ•˜๋ฉด ๋ฌธ์ œ ์‚ฌ์ดํŠธ๋กœ ์ด๋™ํ•ฉ๋‹ˆ๋‹ค.


 

 

๐Ÿ’ฃ ๋ฌธ์ œ ์ดํ•ด

 

 

์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ๋ฅผ ๊ตฌํ•œ ๋’ค, ๋งˆ์„์„ ๋‘ ๊ฐœ๋กœ ๋ถ„ํ• ํ•  ์ˆ˜ ์žˆ๋„๋ก ๋„๋กœ๋ฅผ ์ œ๊ฑฐํ•˜์—ฌ ์ด ์œ ์ง€๋น„๊ฐ€ ์ตœ์†Œ๊ฐ€ ๋˜๋„๋ก ํ•˜๋ฉด ๋œ๋‹ค.

 

์ด ๋ฌธ์ œ๋Š” ํฌ๋ฃจ์Šค์นผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ํ’€์ดํ–ˆ๋‹ค.

 

 

๐Ÿ’ญ ํ’€์ด ๊ณผ์ •

 

 

 

์ž‘์„ฑ ์–ธ์–ด: C++

#include <iostream>
#include <vector>
#include <algorithm>
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<Road> roads;
vector<Road> survived_lines;
int parent[MAX] = {0, };
int depth[MAX] = {0, };

// ์ดˆ๊ธฐ ์„ค์ •
void initialize() {
    for (int i = 0; i <= home_cnt; ++i) {
        parent[i] = i;
        depth[i] = 1;
    }
}

// ๊ฐ€์ค‘์น˜์— ๋”ฐ๋ฅธ ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ
bool compare(const Road &l1, const Road &l2) {
    return l1.weight < l2.weight;
}

// root ๋…ธ๋“œ ์ฐพ๊ธฐ
int findRoot(int node) {
    if (node == parent[node])   return node;
    return parent[node] = findRoot(parent[node]);
}

// ํŠธ๋ฆฌ ํ•ฉ๋ณ‘
void mergeTree(const int node1, const int node2) {
    if (depth[node1] < depth[node2]) {
        depth[node2] += depth[node1];
        depth[node1] = 0;
        parent[node1] = node2;
    }else {
        depth[node1] += depth[node2];
        depth[node2] = 0;
        parent[node2] = node1;
    }
}


int main() {
    int must_deleted = 0;
    int result = 0;
    cin >> home_cnt;
    cin >> road_cnt;
    for (int i = 0; i < road_cnt; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        roads.push_back(Road(a, b, c));
    }
    
    // ๊ฐ€์ค‘์น˜ ๊ธฐ์ค€ ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ
    sort(roads.begin(), roads.end(), compare);
    
    // parent, depth ๋ฐฐ์—ด ์ดˆ๊ธฐํ™”
    initialize();
    
    for (int i = 0; i < road_cnt; ++i) {
        int start_root = findRoot(roads[i].start);
        int dest_root = findRoot(roads[i].dest);
        
        if (start_root != dest_root) {
            result += roads[i].weight;
            survived_lines.push_back(roads[i]);	// ๊ฒฝ๋กœ ํฌํ•จ
            mergeTree(start_root, dest_root);
        }
    }
    
    // ๋น„์šฉ์ด ์ตœ๋Œ€์ธ ๊ฐ„์„ ์„ ์ฐพ์•„์„œ ์ œ๊ฑฐํ•˜๋ฉด
    // ์ตœ์†Œ ์ง‘์ด ํ•˜๋‚˜ ์ด์ƒ์ธ ๋‘ ๋งˆ์„๋กœ ๋ถ„ํ• ํ•  ์ˆ˜ ์žˆ๋‹ค.
    for (int i = 0; i < survived_lines.size(); ++i) {
        must_deleted = max(must_deleted, survived_lines[i].weight);
    }
    
    cout << result - must_deleted << endl;
    
    return 0;
}

 

์ผ๋ฐ˜์ ์ธ ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ ๋ฌธ์ œ์™€ ๋™์ผํ•˜์ง€๋งŒ, ๊ฒฝ๋กœ๋ฅผ ๋”ฐ๋กœ ์ €์žฅํ–ˆ๋‹ค.

์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ์˜ ๊ฐ„์„ ์˜ ํ•ฉ์„ ๊ตฌํ•œ ๋’ค, ๋”ฐ๋กœ ๊ตฌํ•ด๋‘” ๊ฒฝ๋กœ๋“ค์—์„œ ๋น„์šฉ์ด ์ตœ๋Œ€์ธ ๊ฐ„์„ ์„ ์ฐพ์•„์„œ ์ œ๊ฑฐํ•˜๋ฉด ๋œ๋‹ค.

 

 

๐Ÿ† ๋ฐฐ์šด ์ 

 

 

๊ธฐ์กด MST๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ๋“ค๊ณผ ๋น„์Šทํ•˜์ง€๋งŒ ๊ฐ„๋‹จํ•œ ์กฐ๊ฑด์ด ์ถ”๊ฐ€๋œ ๋ฌธ์ œ์˜€๋‹ค.

๋ฌด๋‚œํ•˜๊ฒŒ ํ’€ ์ˆ˜ ์žˆ์—ˆ์Œ!!

์ €์ž‘์žํ‘œ์‹œ ๋น„์˜๋ฆฌ ๋ณ€๊ฒฝ๊ธˆ์ง€ (์ƒˆ์ฐฝ์—ด๋ฆผ)

'Problem_Solving' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[BOJ] ๋ฐฑ์ค€ 2887 ํ–‰์„ฑ ํ„ฐ๋„ / ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ(MST), ํฌ๋ฃจ์Šค์นผ  (0) 2020.11.21
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ๊ฐ€์žฅ ๋จผ ๋…ธ๋“œ / ์ตœ๋‹จ ๊ฒฝ๋กœ, ๋‹ค์ต์ŠคํŠธ๋ผ  (0) 2020.11.21
[BOJ] ๋ฐฑ์ค€ 1922 ๋„คํŠธ์›Œํฌ ์—ฐ๊ฒฐ / ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ(MST), ํฌ๋ฃจ์Šค์นผ  (0) 2020.11.19
[BOJ] ๋ฐฑ์ค€ 14503 ๋กœ๋ด‡ ์ฒญ์†Œ๊ธฐ / ๊ตฌํ˜„  (0) 2020.11.06
[BOJ] ๋ฐฑ์ค€ 2606 ๋ฐ”์ด๋Ÿฌ์Šค / ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰(BFS)  (0) 2020.11.05
    'Problem_Solving' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
    • [BOJ] ๋ฐฑ์ค€ 2887 ํ–‰์„ฑ ํ„ฐ๋„ / ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ(MST), ํฌ๋ฃจ์Šค์นผ
    • [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ๊ฐ€์žฅ ๋จผ ๋…ธ๋“œ / ์ตœ๋‹จ ๊ฒฝ๋กœ, ๋‹ค์ต์ŠคํŠธ๋ผ
    • [BOJ] ๋ฐฑ์ค€ 1922 ๋„คํŠธ์›Œํฌ ์—ฐ๊ฒฐ / ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ(MST), ํฌ๋ฃจ์Šค์นผ
    • [BOJ] ๋ฐฑ์ค€ 14503 ๋กœ๋ด‡ ์ฒญ์†Œ๊ธฐ / ๊ตฌํ˜„
    glowing713
    glowing713

    ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”