어흥

문제 링크: www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 1. 주의할 점 - DFS, BFS, MST, 한줄 모두 가능 - 허무주의 2. 구현 [BFS] - 시작점을 1로 잡고(아무점이나 상관없다) Queue에 넣고 BFS를 수행한다. 방문하지 않은 Node가 있으면 Result++하고 Queue에 넣는다 #include #include #include using namespace std; vector v[1001];..

문제 링크: www.hackerrank.com/challenges/primsmstsub/problem?utm_campaign=challenge-recommendation&utm_medium=email&utm_source=24-hour-campaign Prim's (MST) : Special Subtree | HackerRank Learn to use Prim's algorithm ! www.hackerrank.com 1. 주의할 점 - MST중에서 프림 알고리즘에 대해서 알고 있어야 한다(Edge수가 Node수보다 월등히 많을 때 유리. 반대의 경우, 크루스칼이 유리) 2. 구현 - 간선에 대한 정보를 V[] 벡터에 모두 저장한다 - 간선의 가중치를 기준으로 오름차순으로 정렬되는 우선순위큐 PQ를 생성한..

문제링크: www.hackerrank.com/challenges/kruskalmstrsub/problem Kruskal (MST): Really Special Subtree | HackerRank Learn to use the Kruskal's algorithm ! www.hackerrank.com 1. 주의할 점 - 간선의 가중치가 같다면 각 Node의 합이 작은것을 우선시한다 - Make_union() 함수에서 부모를 잘 갱신하도록 한다 2. 구현 - 입력받는 모든 간선에 대한 정보를 우선순위큐 PQ에 넣는다 - PQ에서 꺼낸 간선에서 양 끝점이 만약 같은 집합이 아니라면 Make_union()함수를 통해 이어주며 Result에는 가중치만큼 더하며 Cnt++를 통해 MST의 경우 Node의 개수-1만..

문제 링크: 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/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..