[G5] 백준 14677번 병약한 윤호 C++ 너비 우선 탐색, 투 포인터, unordered_set

리뷰

 

https://www.acmicpc.net/problem/14677

문자열의 양 끝의 문자를 탐색하며 BLD순으로 제거할 수 있는지 여부를 확인하기 위한 문제

 

 

전역 변수

• Stauts : 현재 왼쪽, 오른쪽 포인터 인덱스와 먹어야 할 약, 먹은 약의 개수를 정의할 구조체
• s : 약 정보를 저장할 문자열 변수
• n : 약을 먹어야 하는 날짜를 저장할 변수
• m : 약의 개수를 저장할 변수
• dt : 약의 인덱스를 저장할 배열
• v : 방문 여부를 체크하기 위한 unordered_set

 

함수

1. bfs

int bfs() {
	queue<Status> q;
	q.push({ 0, m - 1, 0, 0 });
	int mx = 0;

	while (!q.empty()) {
		auto [l, r, cur, cnt] = q.front(); q.pop();
		//cout << l << " " << r << " " << s[l] << " " << s[r] << " " << cur << " " << dt[cur] << " " << cnt << "\n";
		if (l > r) return m;
		if (mx < cnt) mx = cnt;

		if (!v.count(r * 10000 + l)) {
			if (can_eat(s[l], dt[cur])) {
				v.insert(r * 10000 + l);
				q.push({ l + 1, r, cur == 2 ? 0 : cur + 1, cnt + 1 });
			}

			if (can_eat(s[r], dt[cur])) {
				v.insert(r * 10000 + l);
				q.push({ l, r - 1, cur == 2 ? 0 : cur + 1, cnt + 1 });
			}
		}
	}
	return mx;
}

 

너비 우선 탐색을 통해 먹을 수 있는 약의 최대 개수를 반환하기 위한 함수

 

 

문제풀이

1. n, s값을 입력 받고, m의 값을 s의 크기로 저장한다.(3n과도 같다.)
2. bfs함수를 호출한다.
3. 함수 내부에선 Status타입의 큐 q를 초기화 하고, 0, m-1, 0, 0을 push한다.
4. 변수 mx를 0으로 초기화한다.
5. q가 빌때까지 while루프를 수행하고, 변수 l, r, cur, cnt에 현재 요소의 값을 파싱한다.
6. 기저 조건으로 만약 l이 r보다 클 경우 모든 약을 먹은 경우이므로 m을 반환한다.
7. 만약 mx가 cnt보다 작을 경우 mx를 cnt로 저장한다.
8. v에 r*10000 + l값이 존재하지 않을 경우 분기 처리를 수행한다.
9. can_eat함수를 통해 맨 앞의 약을 먹을 수 있는 경우 방문처리 후 l+1, r, cur+1, cnt+1를 q에 push한다.
10. can_eat함수를 통해 맨 뒤의 약을 먹을 수 있는 경우 방문처리 후 l, r-1, cur+1, cnt+1를 q에 push한다.
11. 기저 조건에 도달하지 못하고 while루프가 종료된 경우 mx에 저장된 값을 반환한다.
12. bfs함수의 반환값을 출력한다.

 

트러블 슈팅

1. N이 약의 개수인줄 알고 500이면 문자열 복사를 해도 된다고 판단하였다, 제출 시 시간 초과를 받았다.
2. 투 포인터 전략을 사용하여 고정된 문자열을 순회하는 방법을 사용, v를 통해 방문처리를 확인해 주어 AC를 받았다.

 

참고 사항

1. m은 최대 1500이므로 방문처리 시 r에 값을 곱해줄땐 1500이상의 정수를 사용해 주면 된다.
2. l이 r보다 커진 경우에 대한 분기 처리를 수행해 주어 모든 약을 먹었을때의 분기 처리를 적용해 주었다.
3. q에 cur을 삽입할때 dt배열의 인덱스를 벗어나지 않도록 삼항연산으로 보정해주었다.

 

정답 코드

#include<iostream>
#include<queue>
#include<unordered_set>
using namespace std;

struct Status {
	int l, r, cur, cnt;
};
string s;
int n, m;
char dt[] = { 'B', 'L', 'D' };
unordered_set<int> v;

bool can_eat(char cmp, char cur) {
	//cout << cmp << " " << cur << "\n";
	if (cmp == cur) return true;
	return false;
}

int bfs() {
	queue<Status> q;
	q.push({ 0, m - 1, 0, 0 });
	int mx = 0;

	while (!q.empty()) {
		auto [l, r, cur, cnt] = q.front(); q.pop();
		//cout << l << " " << r << " " << s[l] << " " << s[r] << " " << cur << " " << dt[cur] << " " << cnt << "\n";
		if (l > r) return m;
		if (mx < cnt) mx = cnt;

		if (!v.count(r * 10000 + l)) {
			if (can_eat(s[l], dt[cur])) {
				v.insert(r * 10000 + l);
				q.push({ l + 1, r, cur == 2 ? 0 : cur + 1, cnt + 1 });
			}

			if (can_eat(s[r], dt[cur])) {
				v.insert(r * 10000 + l);
				q.push({ l, r - 1, cur == 2 ? 0 : cur + 1, cnt + 1 });
			}
		}
	}
	return mx;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> s;
	m = s.size();
	cout << bfs();
}