BOJ 14677:: 병약한 윤호 – BFS

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

 

현재까지 왼쪽에서 $l$개를 먹었고 오른쪽에서 $r$개를 먹었다고 하여 약 봉투의 상태를 $(l, r)$로 나타낼 수 있습니다.

따라서 BFS로 $(0, 0)$에서 출발해 제일 먼 상태가 뭔지를 보면 되죠.

인공지능에서 상태공간 하면서 나오는 그런 문제네요. (슬라이딩 퍼즐 같은 거)

 

#include<cstdio>
#include<queue>
#include<utility>
 
 
using namespace std;
 
typedef pair<int, int> Pint;
 
int n;
char pill[1501];
queue<Pint> q;
bool visited[1500][1500];
 
 
int max_pill(void) {
    int time = 0; // 0: breakfast, 1: lunch, 2: dinner
    char s[] = "BLD";
    
    q.push(Pint(0, 0));
    visited[0][0] = true;
    
    int lv = -1, l, r;
    while (!q.empty()) {
        int sz = q.size();
        while (sz--) {
            l = q.front().first;
            r = q.front().second;
            q.pop();
            
            if (l + r < 3*n) {
                if (pill[l] == s[time] && !visited[l+1][r]) {
                    q.push(Pint(l+1, r));
                    visited[l+1][r] = true;
                }
                if (pill[3*n-1-r] == s[time] && !visited[l][r+1]) {
                    q.push(Pint(l, r+1));
                    visited[l][r+1] = true;
                }
            }
        }
        lv++;
        time = (time+1) % 3;
    }
    
    return lv;
}
 
 
int main(void) {
    scanf("%d %s", &n, pill);
    printf("%d", max_pill());
    return 0;
}

 

급하게 짰는데 time 변수 없이 (lv + 1) % 3을 썼으면 되네요.