이 문제는 최소 신장트리 문제이다 이문제의 경우 일부러 프림 알고리즘을 사용해서 풀었다. 프림 알고리즘의 경우 트리들을 계속 이어붙여나가면서 갈수 있는 곳중 최소의 버텍스를 선택해서 계속 트리를 확장해 가는 코드이다. 이전에 게시물에 프림알고리즘에 대해 설명한게 있다. 이문제의 경우는 좌표로 주어지기 때문에 좌표에 인덱스를 부여해주고 거리를 cost로 해서 프림알고리즘을 풀어주면 되는 문제였다
#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;
vector<priority_queue < pair<float, int>, vector<pair<float, int>>, greater<pair<float, int>>>> inputData(101);
int parent[101];
vector<pair<float, float>> stars(101);
float starDistance;
float makeFloat(float x) {
return round(100 * x) / 100;
}
float getDistance(float x1, float y1, float x2, float y2) {
return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}
int findParent(int x) {
if (parent[x] == x)
return x;
else
return parent[x] = findParent(parent[x]);
}
void uni(int x, int y) {
x = findParent(x);
y = findParent(y);
parent[y] = x;
}
bool isSameParent(int x, int y) {
x = findParent(x);
y = findParent(y);
if (x == y)
return true;
else
return false;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
float tmp1, tmp2;
cin >> tmp1 >> tmp2;
stars[i] = { tmp1,tmp2 };
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
float distance = getDistance(stars[i].first, stars[i].second, stars[j].first, stars[j].second);
if (i == j)
continue;
inputData[i].push({ distance, j });
}
parent[i] = i;
}
for (int i = 1; i <= n; i++) {
int star1 = 1;
while (!inputData[1].empty()) {
int star2 = inputData[1].top().second;
float cost = inputData[1].top().first;
inputData[1].pop();
if (!isSameParent(star1, star2)) {
starDistance += cost;
uni(star1, star2);
while (!inputData[star2].empty()) {
inputData[1].push({ inputData[star2].top().first, inputData[star2].top().second });
inputData[star2].pop();
}
break;
}
}
}
cout << round(starDistance*100);
}
이 문제의 경우 최소 신장 트리 문제중 하나로 일단 최소 신장 트리를 만드는 알고리즘으로 크루스칼을 사용해서 풀었다 크루스칼 알고리즘 전전 게시물에 작성했다시피 경로의 Cost가 낮은 경로들 부터 연결을 하지만 서로의 root 가 다른 경로들 만 연결 하고 각자의 root들을 합쳐질때마다 업데이트 해주면 되는 문제 였다
이 문제에서는 핵심적으로 4개의로직이 있다.
1. 부모를 찾는 로직
int findParent(int x) {
if (parent[x] == x)
return x;
else return parent[x] = findParent(parent[x]);
이 로직은 x의 부모 root를찾는 코드로 재귀적으로 부모를 찾으면서 부모를 업데이트도 해주는 코드이다
2. 같은 부모인지 찾는 로직
bool sameParent(int x, int y) {
x = findParent(x);
y = findParent(y);
if (x == y)
return true;
else
return false;
3. 2개의 다른 트리를 합치는 로직 합칠때는 합쳐진 트리의 부모만 바꿔주면 된다
void uni(int x, int y) {
x = findParent(x);
y = findParent(y);
parent[y] = x;
}
4. cost가 낮은 순 부터 오름차순으로 입력 데이터를 정렬 한다 그후 루프를 돌면서 2번 3번 과정을 반복해준다 그후 연결된 cost중 가장 높은부분을 뺴준다 그 이유는 이문제에서 마을을 두개로 분리한다고 하였으니 가장 비용이 많이 드는 길 을 없애면 된다
for (int i = 0; i < inputData.size(); i++) {
if (!sameParent(inputData[i].second.first, inputData[i].second.second)) {
uni(inputData[i].second.first, inputData[i].second.second);
cost += inputData[i].first;
cnt += 1;
if (cnt == v - 1) {
cost -= inputData[i].first;
}
}
}
전체 코드는 아래와 같다
#include<iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 가중치 start end순
vector<pair<int, pair<int, int>>> inputData;
int parent[100001] = { 0, };
int findParent(int x) {
if (parent[x] == x)
return x;
else return parent[x] = findParent(parent[x]);
}
bool sameParent(int x, int y) {
x = findParent(x);
y = findParent(y);
if (x == y)
return true;
else
return false;
}
void uni(int x, int y) {
x = findParent(x);
y = findParent(y);
parent[y] = x;
}
int main() {
int v, e;
long long cost;
cost = 0;
int cnt = 0;
cin >> v >> e;
int tmp1, tmp2, tmp3;
for (int i = 0; i < e; i++) {
cin >> tmp1 >> tmp2 >> tmp3;
inputData.push_back({ tmp3,{tmp1,tmp2} });
}
sort(inputData.begin(), inputData.end());
for (int i = 1; i <= v; i++) {
parent[i] = i;
}
for (int i = 0; i < inputData.size(); i++) {
if (!sameParent(inputData[i].second.first, inputData[i].second.second)) {
uni(inputData[i].second.first, inputData[i].second.second);
cost += inputData[i].first;
cnt += 1;
if (cnt == v - 1) {
cost -= inputData[i].first;
}
}
}
cout << cost;
}
이 문제는 전형 적인 그리디 문제이다 그리디 문제의 특징은 모든 과정에서의 답이아니기 때문에 풀 수 있다
이문제는 일단 주의 할점을 일반적으로 input을 받으면 int 형자료형은 50만자리의 수를 받을 수없기 때문에 string으로 input을 받아 사용하는게 좋다
또한 이문제는 스택을 두고 이전에 들어온 값들보다 현재 들어오는 값들을 뽑고 거기에 넣으면서 뽑은 횟수를 저장해야한다 그래서 만약에 최대 뽑기수보다 못뽑으면 그냥 그상태로 값이 나온다
#include<iostream>
#include<stack>
#include<vector>
#include <algorithm>
using namespace std;
stack<long long> bigStack;
stack<long long> answerStack;
long long n, k;
string num;
vector<long long> arr;
long long popCount=0;
long long result = 0;
int main() {
cin >> n >> k;
cin >> num;
for (int i = 0; i < num.length(); ++i) {
arr.push_back(num[i] - '0'); // 문자 '0'을 빼서 실제 숫자로 변환
}
if(arr.size()!=0)
bigStack.push(arr[0]);
for (long long i = 1; i < n; i++) {
while (!bigStack.empty()&& bigStack.top() < arr[i] && popCount<k) {
bigStack.pop();
popCount += 1;
}
bigStack.push(arr[i]);
}
while (popCount < k) {
bigStack.pop();
popCount += 1;
}
while (!bigStack.empty()) {
answerStack.push(bigStack.top());
bigStack.pop();
}
while (!answerStack.empty()) {
cout << answerStack.top();
answerStack.pop();
}
}
우리가 구해야 할 답은 총 3개다 1 번과 2번은 그냥 우리가 아는 bfs 로 영역의 최대 크기와 영역의 갯수를 구해주면된다 3번은 내가 있는 방을 기준으로 4방의 방에서 벽을 뚫는다고 가정하고 풀었다 그후 모든 방에서 상하좌우방을 뚫었을 때 진행할수 있으면 진행 하도록 코드를 작성 하였다
#include <iostream>
#include<bitset>
#include <queue>
#include <cstring>
using namespace std;
int arr[50][50];
bool isVisited[50][50];
int n, m;
int maxCnt = 1;
int xi[4] = { 0,1,0,-1 };
int yi[4] = { 1,0,-1,0 };
queue<pair<int, int>> bfsq;
bool canGo(int x, int y , int z) {
if (x >= 0 && x < m && y >= 0 && y < n && !isVisited[x][y]) {
if (arr[x][y] & (1 << z)) {
return false;
}
else
return true;
}
return false;
}
bool canGo(int x, int y) {
if (x >= 0 && x < m && y >= 0 && y < n ) {
return true;
}
return false;
}
void bfs(int startX, int startY) {
bfsq.push({ startX,startY });
isVisited[startX][startY] = true;
int cnt = 1;
while (!bfsq.empty()) {
int col = bfsq.front().first;
int row = bfsq.front().second;
bfsq.pop();
for (int i = 0; i < 4; i++) {
if (canGo(col + xi[i], row + yi[i],i)) {
bfsq.push({ col + xi[i] , row + yi[i] });
isVisited[col + xi[i]][row + yi[i]] = 1;
cnt += 1;
if (maxCnt < cnt)
maxCnt = cnt;
}
}
}
}
int main() {
int roomCnt=0;
cin >> n >> m;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (isVisited[i][j])
continue;
roomCnt += 1;
bfs(i, j);
}
}
cout << roomCnt << endl;
cout << maxCnt << endl;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++){
for (int k = 0; k < 4; k++) {
if (canGo(i + xi[k], j + yi[k]) && (arr[i + xi[k]][j + yi[k]] &(1<<k))) {
memset(isVisited, 0, sizeof(isVisited));
arr[i + xi[k]][j + yi[k]] ^= (1 << k);
bfs(i, j);
arr[i + xi[k]][j + yi[k]] |= (1 << k);
}
}
}
}
cout << maxCnt;
}
이 문제는 내가 완전 감을 잘못 잡고 풀고 있었다. 이 문제를 증가수열 비슷하게 풀려고 했었다 하지만 이렇게 풀면 로직이 꼬였는데 테스트케이스 몇개는 잘나왔으나 몇개는 매우 잘 나오지 않았다.
이 문제의 로직은 현재 나를 기준으로 내왼쪽에서의 최대높이와 내오른 쪽의 최대높이를 비교해서 낮은 높이를 선택 해주는 문제 였다 단 오른쪽 과 왼쪽의 최대높이가 나보다는 클때만 빗물이 받아지니 해당 상황일때만 계산하도록 코드를 작성한다 그림으로 나타내면 대충 아래와 같다
해당 로직에 대한 코드는 아래 와 같다
#include <iostream>
#include<algorithm>
using namespace std;
int h, w;
int arr[500];
int main() {
cin >> h >> w;
int result = 0;
for (int i = 0; i < w; i++) {
cin >> arr[i];
}
for (int i = 1; i < w - 1; i++) {
int lmax = 0;
int rmax = 0;
for (int j = 0; j < i; j++) {
if (lmax < arr[j] && arr[j]>arr[i])
lmax = arr[j];
}
for (int j = i + 1; j < w; j++) {
if (rmax < arr[j] && arr[j]>arr[i])
rmax = arr[j];
}
if (lmax != 0 && rmax != 0)
result += min(lmax, rmax) - arr[i];
}
cout << result;
}
