[BAEKJOON] 11659, 11660, 9328

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

 

[sliver 3, 11659 구간 합 구하기 4] - 누적 합(Prefix Sum)

1차원 배열에 대한 누적합 점화식을 활용하여 풀어준다. 누적 합(Prefix Sum)을 모른다면, 위 링크를 통해 배우도록 하자. 시작점과 끝점이 모두 포함되는 관계임에 주의하자

#include <iostream>
#pragma warning(disable:4996)

using namespace std;

int N, M, st, ed;
int num[100001];
int prefixSum[100001];

int main() {
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++) {
		scanf("%d", &num[i]);
	}

	for (int i = 1; i <= N; i++) {
		prefixSum[i] = num[i] + prefixSum[i - 1];
	}

	for (int i = 0; i < M; i++) {
		scanf("%d %d", &st, &ed);
		printf("%d\n", prefixSum[ed] - prefixSum[st - 1]);
	}
}

 

[sliver 1, 11660 구간 합 구하기 5] - 누적 합(Prefix Sum)

1차원 배열에 대한 누적합 점화식을 활용하여 풀어준다. 누적 합(Prefix Sum)을 모른다면, 위 링크를 통해 배우도록 하자.

#include <iostream>
#pragma warning(disable:4996)

using namespace std;

int N, M, sy, sx, ey, ex;
int num[1025][1025];
int prefixSum[1025][1025];

int main() {
	scanf("%d %d", &N, &M);
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			scanf("%d", &num[i][j]);

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			prefixSum[i][j] = num[i][j] 
				+ prefixSum[i - 1][j] 
				+ prefixSum[i][j - 1] 
				- prefixSum[i - 1][j - 1];

	for (int i = 0; i < M; i++) {
		scanf("%d %d %d %d", &sy, &sx, &ey, &ex);
		int calc = prefixSum[ey][ex] 
			- prefixSum[ey][sx - 1] 
			- prefixSum[sy - 1][ex] 
			+ prefixSum[sy - 1][sx - 1];
		printf("%d\n", calc);
	}
}

 

 

[gold 1, 9328 열쇠] - 너비우선탐색(BFS), 비트마스킹

꾀나 다양한 시도가 있었다. [달이 차오른다, 가자] 문제와 동일하게 내가 얻는 Key를 비트마스킹을 활용해 BFS를 적용시키면 됐다. 하지만 둘의 차이점은 Key의 개수에 있었다.

 

6개밖에 되지 않았던 Key로인해 3차원 배열을 활용해 방문탐색을 진행할 수 있었다면, 26개나 되는 Key로 인해 추가적인 배열을 사용할 수 없었다.

 

6개의 비트를 활용하면 111111, 최대 128이 나오지만
26개의 비트를 사용한다면 11111111111111111111111111, 최대 67108863이란 숫자를 사용해야하기 때문이다.

 

발상을 전환해서 내가 얻은 키의 개수를 활용해 보려 했다. <bitset> STL을 활용해 Key의 개수를 파악할 수 있었고 최대 26개의 배열만을 사용할 수 있었기 때문이다. 하지만 이 방법은, 서로 동시에 같은 키의 개수를 획득하였을 때 같은 방문배열을 공유하고 있으므로 적합하지 않았다.

 

이 문제를 해결하기 위해 Priority_queue를 활용했다. 내가 가진 Key의 개수를 기준으로 BFS를 먼저 수행할 수 있게 했다. 하지만 Key의 개수만 놓고 바라봤을 때, ab/cd 같이 개수는 동일하나 서로 다른 Key에 대한 판별을 하기란 쉽지 않았다.

 

그래서 Key의 개수와 Key값을 포함해 새로운 Key가 등장했을 때, 단계적으로 BFS를 진행할 수 있도록 Queue를 초기화 하며 진행했다. 그 결과 시간초과에 부딪히게 되었다.

 

이 과정에서 한 가지를 깨달았다. 단계적으로 BFS를 진행하는 것에 초점을 맞추었을 때, 이번 단계에서 찾을 수 있는 모든 Key를 찾고 그 Key를 기반으로 새로운 BFS를 진행한다면 앞서 말했던 모든 문제가 해결될 수 있었다.

 

그래서 처음 시작하기 전 Key를 갱신하고, 각 단계별로 BFS가 진행될 때 새로운 키를 찾는다면 지속적으로 Key를 갱신했다. 그리고 BFS가 마무리 되었을 때, 갱신된 Key를 활용하여 새로운 BFS를 진행하는 식으로 문제를 해결했다.

 

내가 문제를 해결할 때, 설계한 구조는 다음과 같다.

1) 초기화 및 입력 → init()

2) Key 및 시작점 갱신 → select_entrance(), find_entrance()

3) 각 단계별 BFS 진행 → take_document()

 

*) 문자 Type확인 및 알파벳 변환 → alphabetType(), alphabetTransform()

 

가장 먼저 핵심적인 부분은 Key 갱신이다. Key를 갱신할 땐 '|', Key를 비교할 땐 '&' 비트연산자를 활용해 주어야 한다. 앞서 언급된 [달이 차오른다, 가자] 문제에도 적용되고, 자주 사용되는 방법이기 때문에 숙지하는 것이 좋다. 코드에서 사용된 일부분은 다음과 같다.

// Key 갱신
start_key = start_key | alphabetTransform(map[ny][nx]);
// Key 비교
if (!(key & alphabetTransform(map[ny][nx])))

 

추가적으로 3)번에서 모든 공간에 대해 수십번 반복하기 때문에, 찾아야할 Document에 대한 중복을 방문배열을 활용해 해결해 주어야 한다.

 

전체 풀이 코드는 아래의 '더보기'를 클릭해서 확인하실 수 있습니다.

#include <iostream>
#include <string.h>
#include <queue>
#include <vector>
#pragma warning(disable:4996)

using namespace std;

int H, W, start_key, document;
char map[101][101];
bool visit[101][101];
bool visit_document[101][101];

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

typedef struct data {
	int y, x, key;
}Data;

queue <Data> q;
vector <Data> v;

bool range(int y, int x) {
	return y<0 || x<0 || y>H - 1 || x>W - 1;
}

void init() {
	document = 0;
	start_key = 0;
	memset(visit_document, 0, sizeof visit_document);
	v.clear();
}

string alphabetType(char alphabet) {
	if ('A' <= alphabet && alphabet <= 'Z')
		return "door";
	else if ('a' <= alphabet && alphabet <= 'z')
		return "key";
	else if ('$' == alphabet)
		return "document";
	else
		return "load";
}

int alphabetTransform(char alphabet) {
	int result_key = 0;

	if ('a' <= alphabet && alphabet <= 'z')
		result_key = 1 << (alphabet - 'a');
	else if ('A' <= alphabet && alphabet <= 'Z')
		result_key = 1 << (alphabet - 'A');

	return result_key;
}

void find_entrance(int y, int x) {
	if (map[y][x] != '*') {
		v.push_back({ y, x });
		string alphabet_type = alphabetType(map[y][x]);
		if (alphabet_type == "key") {
			start_key = start_key | alphabetTransform(map[y][x]);
		} else if (alphabet_type == "document" && !visit_document[y][x]) {
			visit_document[y][x] = true;
			document++;
		} 
	}
}

void select_entrance() {
	for (int i = 0; i < H; i++) {
		find_entrance(i, 0);
		find_entrance(i, W - 1);
	}
	for (int j = 1; j < W - 1; j++) {
		find_entrance(0, j);
		find_entrance(H - 1, j);
	}
}

void insert_entrance(int key) {
	memset(visit, 0, sizeof visit);
	for (int i = 0; i < v.size(); i++) {
		Data input = { v[i].y, v[i].x, key };
		if (!visit[input.y][input.x]) {
			visit[input.y][input.x] = true;
			if (alphabetType(map[input.y][input.x]) == "door") {
				if (input.key & alphabetTransform(map[input.y][input.x])) {
					q.push(input);
				}
				continue;
			}
			q.push(input);
		}
	}
}

void take_document() {
	insert_entrance(start_key);

	while (!q.empty()) {
		Data out = q.front(); q.pop();
		for (int d = 0; d < 4; d++) {
			int ny = out.y + dy[d];
			int nx = out.x + dx[d];
			int nk = out.key;
			if (!range(ny, nx) && map[ny][nx] != '*' && !visit[ny][nx]) {
				string alphabet_type = alphabetType(map[ny][nx]);
				if (alphabet_type == "door") {
					if (!(nk & alphabetTransform(map[ny][nx]))) continue;
				}
				else if (alphabet_type == "key") {
					start_key = start_key | alphabetTransform(map[ny][nx]);
				}
				else if (alphabet_type == "document"){
					if (!visit_document[ny][nx]) {
						visit_document[ny][nx] = true;
						document++;
					}
				}
				visit[ny][nx] = true;
				q.push({ ny, nx, nk });
			}
		}
		if (start_key != out.key && q.empty()) {
			insert_entrance(start_key);
		}
	}
}

int main() {
	int tc;
	scanf("%d", &tc);
	for (int t = 0; t < tc; t++) {
		scanf("%d %d", &H, &W);

		init();

		for (int i = 0; i < H; i++) {
			scanf("%s", &map[i]);
		}

		string keyword;
		cin >> keyword;

		for (int i = 0; i < keyword.length(); i++) {
			int new_key = alphabetTransform(keyword[i]);
			start_key = start_key | new_key;
		}

		select_entrance();
		take_document();

		printf("%d\n", document);
	}
}