백준9328_열쇠

문제

상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다.

상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.

• '.'는 빈 공간을 나타낸다.
• '*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
• '$'는 상근이가 훔쳐야하는 문서이다.
• 알파벳 대문자는 문을 나타낸다.
• 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.

마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.

상근이는 빌딩 밖으로 나갈 수 있다. 각각의 문에 대해서, 그 문을 열 수 잇는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.

출력

각 테스트 케이스 마다, 상근이가 훔칠 수 있는 문서의 최대 개수를 출력한다.

예제 입력 

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

[코드]

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class B9328_Key {
 
    public static char[][] building;
    public static boolean [][] visited;
    public static boolean keys[];
    public static HashMap<Integer,ArrayList<Positions>> doors;
    public static int stolen = 0;
    public static int dx[] = {1,-1,0,0};
    public static int dy[] = {0,0,1,-1};
    public static int callcnt=0;
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        
        while(n-->0){
            
            int x = sc.nextInt();
            int y = sc.nextInt();
            
            keys = new boolean[26];
            doors = new HashMap<Integer,ArrayList<Positions>>();
            building = new char[x+4][y+4];
            visited = new boolean[x+4][y+4];
            stolen = 0;
            
            for(int j = 0; j < (x+4); j++){
                String tmp = "";
                if(j>1 && j<(x+2)){
                    tmp = sc.next();
                }
                for(int k = 0 ; k < (y+4); k++){
                    if(j == 0 || j == (x+3) || k == 0 || k == (y+3)){
                        building[j][k] = '*';
                    }else if(j == 1 || j == (x+2) || k == 1 || k == (y+2)){
                        building[j][k] = '.';
                    }
                    else{
                        building[j][k] = tmp.charAt(k-2);
                    }
                }
            }
 
 
            String key = sc.next();
            if(!key.equals("0")){
                for(int j = 0 ; j < key.length(); j++){
                    char c = key.charAt(j);
                    keys[c-97]=true;
                }        
            
            }
            
            getDocuments();
            System.out.println(stolen);
        }
    }
    
    public static void getDocuments(){
        
        Queue<Positions> next = new LinkedList<Positions>();
        next.add(new Positions(1,1));
        visited[1][1] = true;
        
        while(!next.isEmpty()){
        
            Positions P = next.poll();
            
            for(int i = 0 ; i < 4; i++){    
                int nx = P.x+dx[i];
                int ny = P.y+dy[i];
                
                char type = building[nx][ny];
 
                if(type == '*')
                    continue;
                if(visited[nx][ny])
                    continue;
                
                visited[nx][ny] = true;
                
                if(type == '.'){
                        next.add(new Positions(nx,ny));
                }else if(type == '$'){
                    stolen++;
                    next.add(new Positions(nx,ny));
                }
                else{
                    if(type < 97){
                        int pos = type-65;
                        if(keys[pos]){ //키가 있어서 딸 수 있을 경우
                            next.add(new Positions(nx,ny));
                        }else{ //키가 없어서 따지 못할 경우
                            ArrayList<Positions> arr = doors.get(pos);
                            if(arr == null)
                                arr = new ArrayList<>();
                            arr.add(new Positions(nx,ny));
                            doors.put(pos, arr);
                        }
                        
                    }else{
                        int pos = type-97; //이 키가 알파벳 순서로 몇인지
                        keys[pos] = true;
                        next.add(new Positions(nx,ny));
                        if(doors.containsKey(pos)){
                                //문을 딸 수 있는 키가 있으므로, 그 문의 위치를 큐에 넣어줌
                                ArrayList<Positions> arr = doors.get(pos);
                                int ar_size = arr.size();
                                for(int j = 0 ; j < ar_size; j++){
                                    next.add(arr.get(j));
                                }
                            }
                        }
                    }
                }
                
            }
        }
    }
 
 
class Positions{
    
    int x;
    int y;
    
    public Positions(){
    }
 
    public Positions(int x, int y){
        this.x = x;
        this.y = y;
    }
}

[알고리즘]

BFS 를 이용해 풀어보았다. 

전체적인 아이디어는, 문을 마주쳤는데 딸 수 있는 키가 없으면 그 문을 저장해놓는다는 것이다. 

그리고 그 문을 열 수 있는 키를 줏었을 때, 그 문을 큐에 넣어준다.

건물 밖으로 나가서 다른 진입점으로도 갈 수 있어서 빌딩을 둘러싼 복도를 만들어주었다. 그렇게 해서 모든 복도를 돌며 건물안에 있는 모든 진입점을 탐색하게 하는 것이 핵심이당!