이번 문제는 BFS를 통해 해결하였다. 큐에는 (왼쪽 좌표, 오른쪽 좌표, 현재 약, 먹은 약 갯수) 가 들어간다. 중복을 막기 위해 방문처리 리스트를 2차원 리스트로 구현하였다. 방문처리 리스트는 visited[왼쪽 좌표][오른쪽 좌표] 로 구현하였다. while문의 매 반복마다 결과 변수를 cnt와 비교하여 최댓값으로 갱신해주고, 만약 왼쪽 좌표가 오른쪽 좌표보다 커진다면 결과 변수를 반환하도록 하였다. 왼쪽 좌표와 오른쪽 좌표를 확인하여 다음 약 순서와 같고, 방문처리가 되어있지 않다면 방문처리와 함께 큐에 넣어준다. 만약 왼쪽 좌표와 같다면 왼쪽 좌표를 현재+1로, 오른쪽 좌표와 같다면 오른쪽 좌표를 현재-1로 넣어주었다.

Code

from collections import deque
n = int(input())
s = list(str(input()))
nxt = {'B': 'L', 'L': 'D', 'D': 'B'}
def find_max():
    q = deque()
    q.append((0, n*3-1, 'D', 0))
    result = 0
    visited = [[False for _ in range(n*3+1)] for _ in range(n*3+1)]
    visited[0][n*3-1] = True
    while q:
        l, r, cur, cnt = q.popleft()
        result = max(result, cnt)
        if l > r:
            return result
        for i in [l, r]:
            if s[i] == nxt[cur]:
                if i == l and not visited[i+1][r]:
                    visited[i+1][r] = True
                    q.append((i+1, r, nxt[cur], cnt+1))
                elif i == r and not visited[l][i-1]:
                    visited[l][i-1] = True
                    q.append((l, i-1, nxt[cur], cnt+1))
    return result
print(find_max())