백준 9328번 열쇠

KSM_alex·2023년 3월 4일
0

백준

목록 보기
8/9

백준 9328번 링크

문제 풀이

조건이 많아서 BFS 문제처럼 생기긴 했는데 어떻게 풀어야 하나... 고민하다가 main queue, sub queue를 만드는 방식을 생각해냈다.

자료구조

Main queue는 일반적인 BFS에서 사용하는 queue다. Sub queue는 아직 열쇠가 없어서 방문한 적은 있지만, BFS를 수행하지는 못한 cell을 저장한다. 열쇠를 찾았을 때는 sub queue에 있는 모든 cell에 대해 BFS를 수행하면 된다! 열쇠는 'a' ~ 'z'까지 있으므로 sub queue를 총 26개 선언하면 된다.

BFS이므로 방문 여부를 저장하기위해 visited 배열을 선언한다.

열쇠 획득 여부를 판단하기 위해 key 배열을 선언한다.

디버깅

checkCell() 함수

  • visited[r][c], 즉 방문여부를 확인하는 코드를 넣지 않아 수정했다.
  • 열쇠를 획득하는 경우나 문을 연 경우에도 main queue에 push해야 한다.

시간복잡도

가로 크기를 n, 세로 크기를 m이라 하면 O(mn)의 시간복잡도를 가진다.

#include <iostream>
#include <cstring>
#include <deque>
#include <utility>

using namespace std;

deque<pair<int, int>> mainQ;
deque<pair<int, int>> subQ[26];
bool key[26];
char field[100][100];
bool visited[100][100];
int R, C;
int totalCntDocs;

int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, 1, 0, -1 };

void initField(void);
void getInput(void);
void checkSubQ(int n);
void checkCell(int r, int c);
void getMaxDocs(void);

void initField(void) {
	while (!mainQ.empty()) {
		mainQ.pop_back();
	}

	for (int i = 0; i < 26; i++) {
		while (!subQ[i].empty()) {
			subQ[i].pop_back();
		}
	}

	memset(key, false, sizeof(key));
	memset(field, 0, sizeof(field));
	memset(visited, false, sizeof(visited));

	totalCntDocs = 0;
}

void getInput(void) {
	cin >> R >> C;

	for (int i = 0; i < R; i++) {
		cin >> field[i];
	}

	char str[27];
	cin >> str;

	if (str[0] != '0') {
		for (int i = 0; i < strlen(str); i++) {
			key[str[i] - 'a'] = true;
		}
	}
}

void checkSubQ (int n) {
	pair<int, int> p;
	int r, c, nextR, nextC;
	while (!subQ[n].empty()) {
		p = subQ[n].front();
		subQ[n].pop_front();

		r = p.first;
		c = p.second;

		for (int i = 0; i < 4; i++) {
			nextR = r + dr[i];
			nextC = c + dc[i];

			if (0 <= nextR && nextR < R && 0 <= nextC && nextC < C) {
				if (!visited[nextR][nextC])
					checkCell(nextR, nextC);
			}
		}
	}
}

void checkCell(int r, int c) {
	if (visited[r][c]) {
		return;
	}

	visited[r][c] = true;

	if (field[r][c] == '.') {
		mainQ.push_back({ r, c });
	}

	if ('a' <= field[r][c] && field[r][c] <= 'z') {
		key[field[r][c] - 'a'] = true;
		mainQ.push_back({ r, c });
		checkSubQ(field[r][c] - 'a');
	}

	if ('A' <= field[r][c] && field[r][c] <= 'Z') {
		if (key[field[r][c] - 'A']) {
			mainQ.push_back({ r, c });
		}
		else {
			subQ[field[r][c] - 'A'].push_back({ r, c });
		}
	}

	if (field[r][c] == '$') {
		mainQ.push_back({ r, c });
		totalCntDocs++;
	}
}

void getMaxDocs() {
	for (int r = 0; r < R; r++) {
		checkCell(r, 0);
		checkCell(r, C - 1);
	}

	for (int c = 0; c < C; c++) {
		checkCell(0, c);
		checkCell(R - 1, c);
	}

	pair<int, int> p;
	int r, c, nextR, nextC;
	while (!mainQ.empty()) {
		p = mainQ.front();
		mainQ.pop_front();

		r = p.first;
		c = p.second;

		for (int i = 0; i < 4; i++) {
			nextR = r + dr[i];
			nextC = c + dc[i];

			if (0 <= nextR && nextR < R && 0 <= nextC && nextC < C) {
				if (!visited[nextR][nextC])
					checkCell(nextR, nextC);
			}
		}
	}
}

int main(void) {
	int T;

	cin >> T;

	for (int i = 0; i < T; i++) {
		initField();
		getInput();
		getMaxDocs();
		cout << totalCntDocs << endl;
	}

	return 0;
}

0개의 댓글