BOJ 9328, 열쇠

문제 요약

상근이는 건물 내부의 문서를 찾아내는데 문에 맞는 열쇠가 있고 해당하는 열쇠가 있어야만 문을 열고 지나갈 수 있다. </br> ‘.’는 빈 공간을 나타낸다.
‘*‘는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
‘$’는 상근이가 훔쳐야하는 문서이다.
알파벳 대문자는 문을 나타낸다.
알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.

풀이 과정

상근이는 건물 내부와 외부를 드나들 수 있으므로 건물의 가장자리에 드나들 수 있는 통로를 만들어주었다. 상근이가 갖고 있는 열쇠배열 key[]를 만들었고 bfs를 돌면서 문을 만났을 때에는 해당하는 열쇠가 있을 때 queue에 넣고 그대로 진행하며, 만약 문에 맞는 열쇠가 없다면 현재 지나갈 수 없는 문을 저장하는 queue를 따로 만들어 관리하였다.

1. Queue[] door을 만들어 해당하는 열쇠가 있어야만 지나갈 수 있는 문들을 관리한다. (아직 해당 열쇠가 없는상태)
2. bfs를 돌면서 임의의 열쇠를 찾았다면 상근이가 갖고있는 열쇠 배열을 업데이트 해준 후 해당 열쇠를 열수있는 문들의 좌표를 door[]에서 찾은후 원래의 queue에 넣어준다.
3. bfs를 돌면서 임의의 문을 만났다면
   1. 해당 열쇠가 있을 때 -> 그대로 진행,
   2. 해당 열쇠가 없을 때 -> 아직 진행 할 수 없으므로 좌표를 door 큐에 넣는다.
4. 문서를 만났다면 cnt를 1증가시킨다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class P2 {
    static int testCase;
    final static int MX = 105;
    static int h, w;
    static char[][] board = new char[MX][MX];
    static boolean[][] vis = new boolean[MX][MX];
    static String keyStr;
    static int[] dx = {0, -1, 1, 0,};
    static int[] dy = {-1, 0, 0, 1};
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static ArrayList<Integer> ret = new ArrayList<>();

    static class Pair{
        int x, y;
        Pair(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        testCase = Integer.parseInt(br.readLine());
        while(testCase-- > 0){
            Queue<Pair> queue = new LinkedList<>();
            Queue<Pair>[] door = new LinkedList[26];
            int cnt = 0;
            StringTokenizer st = new StringTokenizer(br.readLine());
            h = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());
            for(int i=0; i<h+2; i++) {
                Arrays.fill(board[i], 0, w + 2, '.');
                Arrays.fill(vis[i], 0, w + 2, false);
            }
            for(int i=1; i<=h; i++){
                String str = br.readLine();
                for(int j=1; j<=w; j++){
                    board[i][j] = str.charAt(j-1);
                }
            }
            keyStr = br.readLine();
            int[] key = new int[26];
            if(!keyStr.equals("0")) {
                for(int i=0; i<keyStr.length(); i++){
                    key[keyStr.charAt(i) - 'a'] = 1;
                }
            }
            vis[0][0] = true;
            queue.offer(new Pair(0, 0));
            for(int i=0; i<26; i++){
                door[i] = new LinkedList<>();
            }
            while (!queue.isEmpty()) {
                Pair cur = queue.poll();
                for(int dir =0; dir < 4; dir++){
                    int nx = cur.x + dx[dir];
                    int ny = cur.y + dy[dir];
                    if(nx < 0 || ny < 0 || nx >= h+2 || ny >= w+2) continue;
                    if(board[nx][ny] == '*' || vis[nx][ny]) continue;
                    vis[nx][ny] = true;

                    //열쇠 발견
                    if(board[nx][ny] >= 'a' && board[nx][ny] <= 'z'){
                        int findKey = board[nx][ny] - 'a';
                        key[findKey] = 1;
                        while(!door[findKey].isEmpty()){
                            Pair ndoor = door[findKey].poll();
                            queue.offer(new Pair(ndoor.x, ndoor.y));
                        }
                    }
                    //문 발견
                    else if(board[nx][ny] >= 'A' && board[nx][ny] <='Z'){
                        //todo
                        int t = board[nx][ny] - 'A';
                        if(key[t] == 0){
                            door[t].offer(new Pair(nx, ny));
                            continue;
                        }
                    }
                    //문서 발견
                    else if(board[nx][ny] == '$'){
                        cnt++;
                    }
                    queue.offer(new Pair(nx, ny));
                }
            }
            ret.add(cnt);
        }

        for (Integer integer : ret) {
            System.out.println(integer);
        }

    }
}