# kruskal

20개의 포스트
post-thumbnail

백준 20010 악덕 영주 혜유

문제링크 https://www.acmicpc.net/problem/20010 문제 풀이 크루스칼 알고리즘을 통해 최소신장 트리 만들기 최소신장 트리를 만들면서 최소 신장트리의 연결정보를 linked 배열에 저장 최소신장트리 완성 후 마을 간 연결 정보 중에서 가장 큰 비용을 구하기 위해 dfs를 통해 linked 배열을 탐색 dfs 탐색시 각 단말노드를...

2021년 5월 6일
·
0개의 댓글
post-thumbnail

[프로그래머스/파이썬] (탐욕법(Greedy)) 섬 연결하기

출처n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다.

2021년 5월 3일
·
0개의 댓글
post-thumbnail

[프로그래머스] LV.3 섬 연결하기 (JS)

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를

2021년 4월 10일
·
0개의 댓글

서로소 집합 / 최소 신장 트리

상호배타 집합(겹치지 않는), 교집합x, == 유니온 파인드, 유니크한 식별자를 대표자라고 한다. 서로소 집한 표현 방법 : 연결 리스트, 트리서로소 집합 연산 : Make-Set(단위 연산), Find-Set(x가 속한 집합을 찾는 것, 자신이 속해있는 집합의 대표자

2021년 3월 18일
·
0개의 댓글
post-thumbnail

[백준]#17472 다리 만들기 2

문제섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다

2021년 3월 2일
·
0개의 댓글
post-thumbnail

[Algorithm] BaekJoon : 4386. 별자리 만들기 by Python

문제 바로가기 https://www.acmicpc.net/problem/4386도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.별자리를 이루는 선은 서로 다른 두 별

2021년 2월 22일
·
0개의 댓글
post-thumbnail

[백준]#2887 행성 터널

문제때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA

2021년 2월 19일
·
0개의 댓글
post-thumbnail

[Algorithm] BaekJoon : 1647. 도시 분할 계획 by Python

문제 바로가기 https://www.acmicpc.net/problem/1647동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.마을은 N개의 집과 그 집들을 연

2021년 2월 19일
·
0개의 댓글

[알고리즘] 최소신장트리 (Minimum Spanning Trees)

최소신장트리(Minimum Spanning Tree)는 특정 그래프의 신장트리 중에 가장 최소의 weight을 가지는 신장트리를 뜻한다.여기서 신장트리(Spanning Tree)는 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 최소 연결 부분 그래프를

2021년 1월 30일
·
0개의 댓글
post-thumbnail

[백준]#1774 우주신과의 교감

문제황선자씨는 우주신과 교감을 할수 있는 채널러 이다. 하지만 우주신은 하나만 있는 것이 아니기때문에 황선자 씨는 매번 여럿의 우주신과 교감하느라 힘이 든다. 이러던 와중에 새로운 우주신들이 황선자씨를 이용하게 되었다.하지만 위대한 우주신들은 바로 황선자씨와 연결될 필

2021년 1월 21일
·
0개의 댓글
post-thumbnail

[백준]#2406 안정적인 네트워크

문제한 회사는 본사와 지사의 컴퓨터들을 연결하는 네트워크 시설을 보유하고 있다. 각 지사에는 네트워크용 컴퓨터가 한 대씩 있으며, 이들은 본사의 메인 컴퓨터와 직접 연결되어 있다. 몇몇 지사들끼리 연결되어 있는 경우도 있다.네트워크 시설에서는 두 컴퓨터가 직접 연결되어

2021년 1월 19일
·
0개의 댓글
post-thumbnail

[Algorithm] BaekJoon : 17472. 다리 만들기 2 by Python

문제 바로가기 https://www.acmicpc.net/problem/17472섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.섬은 연결된 땅

2021년 1월 12일
·
0개의 댓글
post-thumbnail

[백준]#10021 Watering the Fields

문제Due to a lack of rain, Farmer John wants to build an irrigation system to send water between his N fields (1 <= N <= 2000).Each field i is des

2020년 12월 4일
·
0개의 댓글

Kruskal 알고리즘 (feat. union-find)

탐욕법(greedy method)의 일종으로 네트워크의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것. MST(최소 비용 신장 트리)를 구할 때 사용된다.간선들을 가중치의 오름차순으로 정렬한다.정렬된 간선들을 차례대로 연결하면서 Cycle을 이루지 않는 간

2020년 11월 5일
·
0개의 댓글
post-thumbnail

[백준]#4386 별자리 만들기

문제도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로

2020년 10월 23일
·
0개의 댓글
post-thumbnail

16202번: MST 게임

간단했다. 크루스칼 문제를 풀어보았다.

2020년 10월 16일
·
0개의 댓글
post-thumbnail

[프로그래머스]#42861 섬 연결하기

문제n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다.

2020년 9월 15일
·
0개의 댓글

[백준]#1197 최소 스패닝 트리

문제그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.입력첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와

2020년 8월 26일
·
0개의 댓글
post-thumbnail

최소신장트리

조건 : 그래프 G는 connected graph이다.정의 : 그래프 G의 spanning tree는 다음 성질을 만족하는 G의 부분 그래프이다.G의 모든 정점들이 포함되어야 한다.connected 그래프이어야 한다.사이클을 포함하지 않아야 한다.신장트리는 다음 두 가

2020년 6월 7일
·
1개의 댓글