[BOJ] 9202 Boggle / Run-Time Check Failure #2 - S 해결

문제: https://www.acmicpc.net/problem/9202

 

 

문제 설명:

 

상하좌우, 대각선 총 8개의 방향으로 이어지는 단어가 사전에 존재하는 단어를 찾아 해당 단어의 길이별로 점수를 매긴다

 

 

각 단어에 속하는 글자 수

1,2 글자 -> 점수는 0점,  but 찾은 단어로 카운트는 해야함

3,4 글자 -> 점수: 1점

5 글자 -> 점수: 2점

6 글자 -> 점수: 3점

7글자 -> 점수: 5점

8글자 -> 점수: 11점

 

 

 

 

 

 

 

 

 

 

 

 

문제 풀이:

1. 사전에 들어있는 단어를 입력 받을 때, trie에 삽입한다.

 boggle 보드에서 abcdef라는  조합이 가능하고 사전에 abcd와 abcde라는 단어가 있을 때 우리는 두 단어 모둘 카운트를 해야한다. 그러므로 트라이에 해당 위치에서 자식이 있는지를 판별하는 child 변수와, 현재 위치에서 단어가 끝남을 나타내는 finish 변수를 추가해준다.

 

 

2. 그 후 각 m 마다 (하나의 보드를 입력받을 때마다) 재귀함수 돌림

보드의 모든 위치에서 시작해서 재귀함수를 돌리는데, 무조건 다 돌리는 것이 아니라 처음 위치가 trie의 root의 next에 속하는 문자인지 판단 후, 속하면 재귀함수를 돌린다. 8방향으로 돌리면서 현재 보는 문자가 현재 보는 트라이의 next에 속하면 트라이를 next로 바꿔주고, 지금 트라이의 finish가 true이면 단어를 찾은 것이므로 set에 해당 문자열을 넣어준다.

 

 

주의 사항:

1. 입력 받을 때, 단어가 최대 8글자라고 char ch[8]; 이렇게 선언하면 Run-Time Check Failure #2 - S 에러가 뜬다

이유: null 값 들어갈 자리가 없어서 

char ch[9]해주면 잘된다.

 

2. 같은 이유로 boggle 보드를 입력 받을 때도 char arr[4][5]; 이렇게 최소한 한 개 이상 크게 선언해야한다. 

(-> 이거 때문에 계속 틀림 ㅠㅠ 오류도 안뜨고 ㅠㅠ 멍청스)

 

3. 한 두 글자 단어가 존재할 때, 점수는 플러스 안해도 찾은 개수로는 플러스 해줘야함

 

 

소스 코드:

struct trie {
	trie* next[26];
	bool finish;
	bool child;

	trie() {
		fill(next, next + 26, nullptr);
		child = finish = false;
	}
	~trie() {
		for (int i = 0; i < 26; i++) {
			if (next[i]) delete next[i];
		}
	}
	void insert(const char* key) {
		if (*key == '\0') {
			finish = true;
			return;
		}
		else {
			child = true;
			int c = *key - 'A';
			if (!next[c]) next[c] = new trie;
			next[c]->insert(key + 1);
		}
	}
};

int n, m;
int dx[8] = { -1,-1,-1,0,0,1,1,1 };
int dy[8] = { -1,0,1,-1,1,-1,0,1 };
char arr[4][5];
bool visit[4][4];
set<string> res;
void func(trie *cur, int curx, int cury, string s) {
	if (s.size() > 8) return;
	if (cur->finish) {
		res.insert(s);
		if (!cur->child || s.size() >= 8)	return;
	}

	for (int i = 0; i < 8; i++) {
		int x = curx + dx[i];
		int y = cury + dy[i];
		if (x < 0 || x >= 4 || y < 0 || y >= 4 || visit[x][y]) continue;
		char c = arr[x][y];
		if (cur->next[c - 'A']) {
			visit[x][y] = true;
			func(cur->next[c - 'A'], x, y, s + c);
			visit[x][y] = false;
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	cin >> n;
	trie* root = new trie;
	for (int i = 0; i < n; i++) {
		char ch[9];
		cin >> ch;
		root->insert(ch);
	}
	cin >> m;
	for (int i = 0; i<m; i++) {
		res.clear();
		for (int j = 0; j < 4; j++) {
			cin >> arr[j];
		}
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				if (root->next[arr[j][k] - 'A']) {
					visit[j][k] = true;
					string t = "";
					func(root->next[arr[j][k] - 'A'], j, k, t + arr[j][k]);
					visit[j][k] = false;
				}
			}
		}
		int sum = 0;
		string resStr = "";
		for (auto next : res) {
			int len = next.size();
			if (len < 3) {}
			else if (len< 5) sum += 1;
			else if (len < 6) sum += 2;
			else if (len < 7) sum += 3;
			else if (len < 8) sum += 5;
			else sum += 11;

			if (len > resStr.size()) resStr = next;
			else if (len == resStr.size()) {
				resStr = resStr > next ? next : resStr;
			}
		}
		cout << sum << " " << resStr << " " << res.size() << '\n';
	}
	return 0;
}