개발윗미

Python으로 구현한 2887번 행성 터널 문제 풀이입니다. https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net # 특정 원소가 속한 집합을 찾기 def find_parent(parent, x) : # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출 if parent[x] != x : parent[x] = find_parent(parent, parent[x]) return parent[x] # 두 ..

[문제] 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었습니다. 왕국은 N개의 행성으로 이루어져 있습니다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 합니다. 행성은 3차원 좌표 위의 한 점으로 생각하면 됩니다. 두 행성 A(Xa, Ya, Za)와 B(Xb, Yb, Zb)를 터널로 연결할 때 드는 비용은 min(|Xa - Xb|, |Ya - Yb|, |Za - Zb|)입니다. 민혁이는 터널을 총 N - 1개 건설해서 모든 행성이 서로 연결되게 하려고 합니다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하세요. [입력 조건] 1. 첫째 줄에 행성의 개수 N이 주어집니다. (1

[문제] 한 마을은 N개의 집과 M개의 도로로 구성되어 있습니다. 각 집은 0번부터 N - 1번까지의 번호로 구분됩니다. 모든 도로에는 가로등이 구비되어 있는데, 특정한 도로의 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일합니다. 예를 들어 2번 집과 3번 집 사이를 연결하는 길이가 7인 도로가 있다고 해봅시다. 하루동안 이 가로등을 켜기 위한 비용은 7이 됩니다. 정부에서는 일부 가로등을 비활성화하되, 마을에 있는 임의의 두 집에 대하여 가로등이 켜진 도로만을 절약하고자 합니다. 마을의 집과 도로 정보가 주어졌을 때, 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력하는 프로그램을 작성하세요. [입력 조건] 1. 첫째 줄에 집의 수 N(1

[문제] 동물원에서 막 탈출한 원숭이 한 마리가 세상 구경을 하고 있다. 어느 날 원숭이는 '평화로운 마을'에 잠시 머물렀는데 마침 아르 사람들은 도로 공사 문제로 머리를 맞대고 회의 중이었다. 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 길마다 길을 유지하는데 드는 유지비가 있다. 마을의 이장은 마을을 2개의 분리된 마을로 분할할 계획을 세우고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다. 그렇게 마을의..

[신장 트리란 ?] 신장 트리는 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. [크루스칼 알고리즘이란 ?] 크루스칼 알고리즘은 대표적인 최소 신장 트리 알고리즘이다. 그리디 알고리즘으로 분류가 되며, 동작 과정은 다음과 같다. 1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. 만약, 사이클이 발생하지 않는다면 최소 신장 트리에 포함시키고, 사이클이 발생한다면 최소 신장 트리에 포함시키지 않는다. 3. 모든 간선에 대하여 2번의 과정을 반복한다. 구체적인 동작 과정은 아래의 게시물에서 확인할 수 있다. https://unie2.tistory.com/37?category=873806 크루스칼 ..

크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 즉, 크루스칼 알고리즘은 최소 비용 신장 트리를 만들기 위한 대표적인 알고리즘이다. 그림과 같은 그래프에서 정점은 7개, 간선은 11개 이다. 가장 적은 비용으로 모든 노드를 연결하는 최소 비용 신장 트리를 만들 때 사용되는 간선의 개수는 6개 이다. 즉, 최소 비용 신장 트리를 만들 때 사용되는 간선의 개수는 노드 개수 -1 이다. 최소 비용 신장 트리는 거리를 기준으로 오름차순 정렬을 한 후 그래프를 연결함으로써 만들 수 있다. 주의할 점은 정렬된 순서에 맞게 그래프에 포함시키기 전에 사이클이 형성되면 안된다. 그렇기 때문에 사이클 테이블을 먼저 확인한 후, 만약 사이클을 형성하는 경우에는 간선을 포함하지 않도록..