[백준] 열쇠(9328)

문제 링크 : [백준] 열쇠(9328)

문제 설명

h * w의 격자가 주어지고, 각 칸은 이동할 수 있는 공간, 벽, 열쇠, 문, 문서로 구성됩니다.
벽을 통과하지 못하며, 문은 문과 매칭되는 열쇠를 가지고 있는 경우에만 이동 할 수 있습니다.
대문자 문을 열기 위해서는 그의 소문자 열쇠를 가지고 있어야합니다.
건물 밖에서 들어가야 하며, 처음 가지고 있는 열쇠도 주어집니다.
이런 상황이 주어졌을 때, 문서를 최대 몇개까지 가질 수 있는지 구하세요.

입력

T(테스트 케이스의 수, 1 <= T <= 100)
H(격자의 높이, 1 <= H <= 100)
W(격자의 너비, 1 <= W <= 100)
격자 정보(*은 벽, .은 빈 칸, 대문자는 문, 소문자는 열쇠, $는 문서)
가지고 있는 키 정보

3
5 17
*****************
.............**$*
*B*A*P*C**X*Y*.X.
*y*x*a*p**$*$**$*
*****************
cz
5 11
*.*********
*...*...*x*
*X*.*.*.*.*
*$*...*...*
***********
0
7 7
*ABCDE*
X.....F
W.$$$.G
V.$$$.H
U.$$$.J
T.....K
*SQPML*
irony

출력

3
1
0

카테고리

#BFS

시간 복잡도 상한

테스트케이스 때문에 O(N³) 정도 될 것 같습니다.

해결 방법

1. 기본적인 그래프 탐색과 비슷한 구조입니다.
2. 단, 상황에 따라서(열쇠는 가지고 있는지 없는지) 노드를 방문 할 수도 있고, 없을 수도 있습니다.
3. 자칫 잘못하면 타이밍(열쇠를 습득하면 다시 다 돌아야 되나?)까지 모두 고려해야 될 것 같습니다.
4. 문이 있다면, 현재 열쇠가 있으면 바로 BFS를 이용하여 노드 탐색을 계속 하고, 열쇠가 없다면, 다음에 열쇠를 습득하면 바로 탐색을 할 수 있도록 vector를 이용하여 관리합니다.
5. 열쇠를 습득한다면, 그 열쇠로 열 수 있는 모든 곳(4에서 관리된 문들)을 큐에 넣어 BFS로 탐색을 하도록 합니다.

시간복잡도

O(N)

코드

#include<cstdio>
#include<queue>
#include<vector>
#include<string.h>
#define P pair<int,int>
using namespace std;
int t,n,m,i,j,w[27],a,o[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
char s[102][102],x[27];
vector<P>v[27];
queue<P>q;
void md(int x,int y){
    char c=s[x][y];
    if(c=='.')q.push({x,y});
    if(c>='A'&&c<='Z'){
        if(w[c-'A'])q.push({x,y});
        else v[c-'A'].push_back({x,y});
    }
    if(c>='a'&&c<='z'){
        q.push({x,y});
        w[c-'a']=1;
        for(P z:v[c-'a'])q.push(z);
        v[c-'a'].clear();
    }
    if(c=='$')a++,q.push({x,y});
    s[x][y]='*';
}
int main(){
    scanf("%d",&t);
    while(t--){
        memset(w,0,sizeof(w));
        for(a=i=0;i<27;i++)v[i].clear();
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)scanf("%s",s[i]+1);
        scanf("%s",x);
        for(i=0;x[i];i++)if(x[i]>='a'&&x[i]<='z')w[x[i]-'a']=1;
        for(i=1;i<=n;i++)md(i,1),md(i,m);
        for(i=2;i<m;i++)md(1,i),md(n,i);
        while(!q.empty()){
            P cur=q.front();q.pop();
            for(i=0;i<4;i++)md(cur.first+o[i][0],cur.second+o[i][1]);
        }
        printf("%d\n",a);
    }
}