용꿀
꼬마개발자허니
용꿀
전체 방문자
오늘
어제
  • 분류 전체보기 (250)
    • 개발 (77)
      • 스프링 입문 (7)
      • 스프링 기본 (9)
      • ToDo List using JPA (2)
      • 스프링 개념 (9)
      • 스프링 부트와 AWS로 혼자 구현하는 웹 서비스 (8)
      • 스프링 MVC (3)
      • CS (21)
      • 개발 팁 (8)
      • 스프링 MSA (5)
      • 곰터뷰🐻 (5)
    • 알고리즘 (169)
      • 알고리즘 문제 풀이 (165)
    • 잡동사니 (1)
      • 노래 가사 (1)
hELLO · Designed By 정상우.
용꿀

꼬마개발자허니

(C++) 백준 1368번 - 물대기
알고리즘/알고리즘 문제 풀이

(C++) 백준 1368번 - 물대기

2023. 6. 19. 12:50

문제 링크 : https://www.acmicpc.net/problem/1368

 

1368번: 물대기

첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어

www.acmicpc.net

풀이

새로운 우물을 파는 것은 새로운 정점을 하나 추가하여 그에 맞는 cost를 가지는 간선을 추가하는 방식으로 진행하였다.

Union-Find를 사용해서 크루스칼 알고리즘을 구현하여 최소 신장 트리의 크기를 구해보았다.

#include <iostream>
#include <algorithm>
#include <tuple>

using namespace std;

tuple<int, int, int> t[100005];
int n, e, cost, result, cnt;
int parent[305];

int find(int x){
    if(parent[x] == x) return x;
    else return parent[x] = find(parent[x]);
}

void uni(int x, int y){
    x = find(x);
    y = find(y);
    parent[y] = x;
}

bool is_diff_group(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y) return false;
    else return true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> cost;
        t[e++] = {cost, i, n+1};
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> cost;
            if(i >= j) continue;
            t[e++] = {cost, i, j};
        }
    }
    n++;
    sort(t, t+e);
    for(int i = 1; i <= n; i++) parent[i] = i;
    for(int i = 0; i < e; i++){
        if(!is_diff_group(get<1>(t[i]), get<2>(t[i]))) continue;
        uni(get<1>(t[i]), get<2>(t[i]));
        result += get<0>(t[i]);
        cnt++;
        if(cnt == n-1) break;
    }
    cout << result;
}

'알고리즘 > 알고리즘 문제 풀이' 카테고리의 다른 글

(JAVA) 백준 2805번 - 나무 자르기  (1) 2023.12.27
(C++) 백준 9372번 - 상근이의 여행  (0) 2023.06.20
(C++) 백준 1197번 - 최소 스패닝 트리  (0) 2023.06.19
(C++) 백준 2252번 - 줄 세우기  (0) 2023.06.19
(C++) 백준 1260번 - DFS와 BFS  (1) 2023.06.19
    '알고리즘/알고리즘 문제 풀이' 카테고리의 다른 글
    • (JAVA) 백준 2805번 - 나무 자르기
    • (C++) 백준 9372번 - 상근이의 여행
    • (C++) 백준 1197번 - 최소 스패닝 트리
    • (C++) 백준 2252번 - 줄 세우기
    용꿀
    용꿀

    티스토리툴바