어흥

문제 링크: https://www.acmicpc.net/problem/10021 10021번: Watering the Fields Input Details There are 3 fields, at locations (0,2), (5,0), and (4,3). The contractor will only install pipes of cost at least 11. Output Details FJ cannot build a pipe between the fields at (4,3) and (5,0), since its cost would be only 10. He therefore b www.acmicpc.net 1. 주의할 점 - MST문제로, MST 생성할 수 없다면 -1을 출력한다 2. 구현 - 크루..

문제 링크: https://www.acmicpc.net/problem/11085 11085번: 군사 이동 문제 전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비가 존재�� www.acmicpc.net 1. 주의할 점 - 가중치가 큰 간선들부터 연결을 한다 - 크루스칼 알고리즘을 사용한다. 단, 종료조건이 다르다 2. 구현 - 입력 받는 간선에 대한 정보를 우선순위큐에 저장하며, 가중치의 내림차순으로 정렬한다 - 우선순위큐에서 간선에 대한 정보를 1개씩 빼면서 만약 2개의 도시가 이어져 있지 않다면 연결하고, Result에 해..

문제 링크: https://www.acmicpc.net/problem/4650 4650번: Jungle Roads The input consists of one to 100 data sets, followed by a final line containing only 0. Each data set starts with a line containing only a number n, which is the number of villages, 1 < n < 27, and the villages are labeled with the first n letters of the a www.acmicpc.net 1. 주의할 점 - 매 TC마다 Par[] 배열 초기화 - MST 알고리즘에 대해 알고 있어야 한다 2. 구현..

문제 링크: https://www.acmicpc.net/problem/2406 2406번: 안정적인 네트워크 첫째 줄에 두 정수 n(1≤n≤1,000), m이 주어진다. n은 컴퓨터의 개수이며, m은 연결되어 있는 지사 컴퓨터들의 쌍의 개수이다. 다음 m개의 줄에는 두 정수 x, y가 주어진다. 이는 서로 다른 두 컴퓨터, www.acmicpc.net 1. 주의할 점 - 1번 Node를 제외하고 MST를 만든다 - 총 Node-2개의 간선이 만들어지면 된다(Cycle을 생성하는 간선은 개수에 포함 안함) 2. 구현 - 크루스칼 알고리즘을 통해 MST 문제를 해결한다 - 이미 연결된 지사의 컴퓨터 중, 같은 부모를 공유하고 있지 않다면 Make_union(a,b) 함수를 통해 같은 부모를 공유하도록 설정하..

문제 링크: https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 문제 황선자씨는 우주신과 교감을 할수 있는 채널러 이다. 하지만 우주신은 하나만 있는 것이 아니기때문에 황선자 씨는 매번 여럿의 우주신과 교감하느라 힘이 든다. 이러던 와중에 새로운 우� www.acmicpc.net 1. 주의할 점 - MST 알고리즘에 대해 알고 있어야 한다 - 이미 연결되어 있는 경우, 어떻게 처리할 것인지 고민한다 2. 구현 - 크루스칼 알고리즘을 통해 MST를 해결한다 - 모든 우주신들의 좌표를 X[], Y[] 배열에 저장한다 - 이미 연결된 통로의 정보를 입력받아 Make_union(a,b) 함수를 통해 A와 B의 부모를 일치시킨다 - 서로 다른 신과 그 사이의 거리를 Ca..

문제 링크: https://www.acmicpc.net/problem/6497 6497번: 전력난 문제 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈�� www.acmicpc.net 1. 주의할 점 - 모든 간선의 총합 - MST를 연결할때 드는 최소 비용을 출력한다 - 매 TC마다 Par[] 배열을 초기화 한다 2. 구현 - 크루스칼 알고리즘을 통해 MST를 구현한다 - 입력받는 모든 간선에 대한 정보를 우선순위 큐에 삽입하고, 간선의 가중치가 오름차순이 되도록 정렬한다 - Find_parent(int x) 함수를 통해 X의 부모를 반환한다 - Make_union(in..

문제 링크: https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 1. 주의할 점 - MST 알고리즘에 대해 알고 있어야 한다(필자는 크루스칼 알고리즘을 통해 풀 예정이다) 2. 구현 - 크루스칼 알고리즘을 통해 해당 문제를 해결한다 - Find_parent(int x) 함수를 통해 X의 부모를 반환한다 - Make_union(int a, int b) 함수를 통해 A와 B의 부모가 일치하지 않는다면, 부모의 수가 작은쪽으로 합친다 - 입력받은 간선의 정보를 모두 우선순위큐에 넣고 간선의 크기가 작은것부터 뽑아서 사용한다 - Cycle이 생..

문제 링크: https://www.acmicpc.net/problem/2887 2887번: 행성 터널 문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 www.acmicpc.net 1. 주의할 점 - MST 문제로, 프림 혹은 크루스칼 알고리즘에 대하여 알고 있어야 한다. 여기서는 크루스칼 사용 - X..