14621. 나만 안되는 연애 문제 풀이 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 최소 스패닝 문제에서 서로 다른 타입의 노드만 연결할 수 있다는 조건 하나를 추가한 문제! 어렵지 않게 풀 수 있었다. 알고리즘 설계 W인지 아닌지 판별하는 bool형 배열을 만들고 입력받는다. 간선을 입력받을 때, 서로 다른 노드라면 간선 배열에 저장해준다. 간선들을 가중치 기준으로 오름차순으로 정렬한다. 사이클이 생기지 않게 크루스칼 알고리즘으로 최소 스패닝 트리의 비용을 구한다..
1774. 우주신과의 교감 문제 풀이 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 지금까지와는 다르게, 가중치가 주어지지 않고 점과 점 사이의 거리가 가중치인 문제였다. 크루스칼을 구현하는 능력이 부족한 것 같아, 크루스칼 알고리즘을 이용해서 구현해봤다. 알고리즘 설계 노드의 번호, x, y 좌표를 저장해준다. 저장한 노드들 사이에 모든 간선을 구한다. 간선 = { A노드, B노드, A와 B 사이의 거리 (가중치) } 구한 간선들을 가중치를 기준으로 오름차순 정렬해준다. 사이클이..
21924. 도시 건설 문제 풀이 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net 전체 간선의 비용 - MST의 비용을 구하는 문제! 쉬워 보이는 문제였다만, 다만... 모든 노드가 연결되어있지 않으면 -1을 출력해야 하는 조건 때문에 조금 고민을 했다. 알고리즘 간선의 수가 꽤 많았기 때문에, 프림 알고리즘을 사용하였다. 모든 노드가 연결되지 않을 때를 처리해주기 위해, 그때 발생하는 일..
16398. 행성 연결 문제 풀이 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 갑자기 N x N 행렬이 나와서 당황했지만... 문제를 천천히 알고보니 각 노드들을 서로 서로 잇는 간선의 가중치값이 있는 행렬이었고... 이런 구조는 프림 알고리즘에서 잘 볼 수 있는 구조이다! 만약 이런 트리가 있다고 한다면, 프림 알고리즘에서는... 이렇게 한 노드를 중심으로 연결된 노드와 그 간선의 가중치를 저장해주기 때문에!! 가중치를 저장한 행렬과 비슷하다고 볼 수 있었다. 그래서 프림 알고리즘을 이용해 풀어봤다. #i..
1647. 도시 분할 계획 문제 풀이 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 문제가 길지만... 해석해보면 하나의 최소 신장 트리를 두 개로 나눴을 때, 최소 간선의 수를 구하는 것이다. 사실 처음에는 조금 어렵다고 느꼈지만... 시각적으로 최소 스패닝 트리를 보니 어떻게 구현해야할지 바로 알 수 있었다! 이 트리를 보니, 확실히 알았다. 이 트리에서 두 개의 최소 신장 트리로 분할하려면 어떻게 해야할까? 일단, 간선 하나를 제거해야할 것이다. 그래야 두 개로 나..
1922. 네트워크 연결 문제 풀이 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 단순 최소 스패닝 트리를 구하는 문제! 위 문제처럼 크루스칼이나 프림을 사용하면 된다고 생각해, 좀 더 쓰기 번거롭지 않은 크루스칼 + 메모이제이션을 이용했다. 코드 #include #include #include using namespace std; int parents[1001]; // 간선 struct Edge { int a, b, w; bool operator < (const Edge& e) const { return w < e.w; } }; // 최상위 부모 찾기 int find(int v) { vector..
최소 스패닝 트리 1197. 최소 스패닝 트리 문제 풀이 (크루스칼) 문제 풀이 (프림) 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 자료구조와 알고리즘 시간에 최소 스패닝 트리 개념과 크루스칼, 프림 알고리즘을 배워서 풀어본 문제! 크루스칼은 메모이제이션을 이용해야 통과가 되었고, 프림은 구현만 해도 통과가 되는 문제였다! 첫 문제니까... 알고리즘 설명을 해보자 하면 1. 크루스칼 간선들을 가중치 기준으로 오름차순 정렬해서 선택하는 알고리즘! 쉬워 보이지만..
