[BAEKJOON] 11286, 1251, 14938, 1715, 2665

※ 소스코드는 각 문제 설명 하단에 <더보기>를 통해 확인하실 수 있습니다.

 

[sliver1, 11286 절대값 힙] - 우선순위 큐

문제를 품에 별 어려움은 없으나, 우선순위 큐를 사용할 때 커스텀 정렬을 사용하고 싶다면

C++에서는 무조건 "struct compare"로 선언할 것을 명심하자

#include <iostream>
#include <queue>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;

int N, num;
struct Data {
	int value;
	int type;
};
struct compare {
	bool operator()(Data a, Data b) {
		if (a.value == b.value) {
			return a.type > b.type;
		}
		return a.value > b.value;
	}
};
priority_queue <Data, vector<Data>, compare> pq;

int main() {
	scanf("%d", &N);
	for (int n = 0; n < N; n++) {
		scanf("%d", &num);
		switch (num) {
		case 0:
			if (pq.empty()) printf("0\n");
			else {
				Data out = pq.top(); pq.pop();
				printf("%d\n", out.value * out.type);
			}
			break;
		default:
			pq.push({ abs(num), num < 0 ? -1 : 1 });
			break;
		}
	}	
}

 

[sliver5, 1251 단어 나누기] - 브루트포스

c++을 사용하는 경우, string 타입을 활용할 때 reverse method는 algorithm 헤더에 있는 것에 유의하자
또한 substr method는 인자로 받는 두 수를 (a, b)라 할 때, 시작위치 a에서 b 길이만큼의 문자열을 분할하겠다는 의미임에 유의하자

#include <iostream>
#include <string>
#include <algorithm>
#pragma warning(disable:4996)
using namespace std;

string word, answer;
string reverse_word[3];

int len;
int slice_pivot[2];
bool visit[51];

void selectSlicePivot(int value, int cnt);
string reverseWord();

int main() {
	cin >> word;
	len = word.length();
	for (int i = 0; i < len; i++) answer += 'z';
	selectSlicePivot(0, 0);
	cout << answer;
}

void selectSlicePivot(int value, int cnt) {
	if (cnt == 2) {
		string new_answer = reverseWord();
		if (answer.compare(new_answer) > 0) {
			answer = new_answer;
		};
		return;
	}
	for (int i = value; i < len - 1; i++) {
		if (!visit[i]) {
			visit[i] = true;
			slice_pivot[cnt] = i;
			selectSlicePivot(i, cnt + 1);
			visit[i] = false;
		}
	}
}

string reverseWord() {
	string st = word.substr(0, slice_pivot[0] + 1);
	string mid = word.substr(slice_pivot[0] + 1, slice_pivot[1] - slice_pivot[0]);
	string ed = word.substr(slice_pivot[1] + 1, len - slice_pivot[1]);
	reverse(st.begin(), st.end());
	reverse(mid.begin(), mid.end());
	reverse(ed.begin(), ed.end());
	return st + mid + ed;
}

 

 

[gold4, 14938 서강그라운드] - 플로이드 와샬

각 지점끼리 연결된 길은 양방향이기 때문에, 
플로이드 와샬 배열에 추가할 때 양방향으로 추가할 수 있도록 신경써야 한다.

#include <iostream>
#include <queue>
#pragma warning(disable:4996)
using namespace std;

#define MAX 101

int N, M, R;
int item[101];
int floyd[101][101];

void init() {
	scanf("%d %d %d", &N, &M, &R);
	for (int n = 1; n <= N; n++) scanf("%d", &item[n]);

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			floyd[i][j] = MAX;

	int st = 0, ed = 0, value = 0;
	for (int r = 0; r < R; r++) {
		scanf("%d %d %d", &st, &ed, &value);
		floyd[st][ed] = value;
		floyd[ed][st] = value;
	}
}

void floydwarshall() {
	for (int k = 1; k <= N; k++)
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= N; j++) {
				if (i != j && floyd[i][j] > floyd[i][k] + floyd[k][j]) {
					floyd[i][j] = floyd[i][k] + floyd[k][j];
				}
			}
}

int answer = 0;
void solve() {
	for (int i = 1; i <= N; i++) {
		int cnt = 0;
		for (int j = 1; j <= N; j++) {
			if (i == j) {
				cnt += item[j];
				continue;
			}
			if (floyd[i][j] <= M) {
				//printf("%d->%d is get %d items!\n", i, j, item[j]);
				cnt += item[j];
			}
		}
		//printf("%d point can get total %d items!\n", i, cnt);
		answer = answer > cnt ? answer : cnt;
	}
	printf("%d", answer);
}

int main() {
	init();
	floydwarshall();
	solve();
}

 

[gold4, 1715 카드 정렬하기] - 우선순위 큐

별거없다.

#include <iostream>
#include <queue>
#pragma warning(disable:4996)
using namespace std;

int N, card;

struct compare {
	bool operator()(int a, int b) {
		return a > b;
	}
};
priority_queue <int, vector<int>, compare> pq;

int main() {
	scanf("%d", &N);
	for (int n = 0; n < N; n++) {
		scanf("%d", &card);
		pq.push(card);
	}

	int answer = 0;
	while (true) {
		int fs = 0, se = 0;
		fs = pq.top(); pq.pop();
		if (!pq.empty()) {
			se = pq.top(); pq.pop();
		}
		else {
			break;
		}
		answer += fs + se;
		pq.push(fs + se);
	}

	printf("%d", answer);
}

 

[gold4, 2665 미로만들기] - BFS(너비 우선 탐색) + 우선순위 큐

검정색 방에 대해 0~최대 51개까지의 방을 직접 선택하는 조합으로 문제를 풀려하면,
정말 쉽게 시간초과를 얻을 수 있다.

그래서 본인은 다음의 우선순위를 가지는 큐를 활용하여 문제를 풀었다.
1. 검은색 방을 지나왔던 카운트 기준 최소값 우선 탐색
2. 흰색 방 우선 탐색
이렇게 된다면, 문제에서 원하는 검은방을 최소로 뚫으면서 흰색방을 우선 탐색할 수 있다.

위 방법 이외에도 검은색 방을 카운팅하여 3차원 배열을 통한 풀이법도 있을 것 같다.

#include <iostream>
#include <queue>
#pragma warning(disable:4996)
using namespace std;

int N;
int map[51][51];

int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };

typedef struct data {
	int y, x, type, cnt;
}Data;
struct compare {
	bool operator()(Data a, Data b) {
		if (a.cnt == b.cnt) {
			return a.type < b.type;
		}
		return a.cnt > b.cnt;
	}
};

bool range(int y, int x) {
	return y < 0 || x<0 || y>N - 1 || x>N - 1;
}
void bfs() {
	priority_queue <Data, vector<Data>, compare> q;
	bool visit[51][51] = { 0, };
	q.push({ 0, 0, map[0][0], 0});
	visit[0][0] = true;
	while (!q.empty()) {
		Data out = q.top(); q.pop();
		if (out.y == N - 1 && out.x == N - 1) {
			printf("%d", out.cnt);
			return;
		}
		for (int d = 0; d < 4; d++) {
			int ny = out.y + dy[d];
			int nx = out.x + dx[d];
			if (!range(ny, nx) && !visit[ny][nx]) {
				visit[ny][nx] = true;
				q.push({ ny, nx, map[ny][nx], map[ny][nx] == 0 ? out.cnt + 1 : out.cnt });
			}
		}
	}
}

int main() {
	scanf("%d", &N);
	char temp[51];
	for (int i = 0; i < N; i++) {
		scanf("%s", &temp);
		for (int j = 0; j < N; j++) {
			map[i][j] = temp[j] - '0';
		}
	}
	bfs();
}