9328번 : 열쇠 [JAVA]

문제링크

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

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

입력

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

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

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

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

상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.

출력

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

예제 입력 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

예제 출력 1 복사

3
1
0

성공 여부(걸린 시간): 성공 (56분 37초)

아이디어

이 문제는 친구가 풀어보면 좋을 것 같다고 생각이 들어 풀어보게 되었다.
그런데 읽다보니 얼마전에 풀었던 불마전에 풀었던 11967번: 불켜기와 거의 같은 문제라고 봐도 무방할 정도의 문제였다.

아무튼 전체 코드구조는 처음에 어떻게 구상했냐면 크게 보면 케이스 수만큼 입력 + BFS + 출력저장 끝이다. 골드 1치고는 쉬운 문제인듯 하다.

1. 전체 테스트케이스만큼 돌아주는 반복문
   1. 해당 케이스에서 받아야할 입력 처리
      => 입력은 전부 char 배열에 넣어주었다. 그리고 마지막줄에 등장하는 key List는 char로 인자반복을 하며
      keys라는 HashMap에 Integer Type으로 'a'를 빼주어 저장해주었다. 이는 추후에 대문자인 문을 지날 수 있는지 검사할때나 추가하고
      할때에 나름대로 편하게 하기 위함이다.
   2. 입력처리가 전부 끝났다면 이제 BFS를 돌아준다.
      => BFS는 우선 현재의 노드(int배열타입으로 해주었음)를 poll하여 현재 좌표 기준으로 만약 문이나 열쇠일 경우에 처리를 먼저 해주도록 했다.
      if(대문자 알파벳)
      -> 현재 상근이의 좌표가 문에 위치하고 있다는 것인데 이 문을 만약 열수있는 해당 문의 소문자 열쇠가 존재하는지 검사해준다. 없다면 이번 노드는 넘기기
      else if(소문자 알파벳)
      -> 현재 상근이가 열쇠를 주웠다는 의미 새로운 열쇠임이 확인된다면 방문표시배열 초기화를 해주고 열쇠를 저장해준다음 다시 0,0부터 BFS시작하도록 세팅해줌 (열쇠가 있던 자리를 '.'으로 대체할 경우 20ms빨라졌음, 그러나 큐 자체를 비우니 오히려 메모리 사용과 시간이 증가함. 이유는 생각해보면 어차피 문을 열 수 있는 경우가 증가한다고 해서 기존에 갔던 길에 대해서 못갈 상황은 발생하지 않기에 굳이 clear를 해줄 필요도 없고 쓸데없는 연산만 증가시킨다.)
      else if($)
      -> dollar++; 해주고 해당 배열'.'로 변경해줌
   3. 그다음에는 이동할 수 있는 방향에 대해서 for문을 통해 상하좌우를 이동할 수 있는지 검사하고 방문처리 후 q.add() 해주었다.
2. 결과 저장한 StringBuilder 출력해주고 종료 ^^

최종 코드

import java.io.*;
import java.util.*;

class Main {
    static int H,W;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        int [] dx = {1, 0, -1, 0};
        int [] dy = {0, 1, 0, -1};
        StringBuilder sb = new StringBuilder ();
        while(T--!=0){
            StringTokenizer hw = new StringTokenizer(br.readLine());
            H = Integer.parseInt(hw.nextToken());
            W = Integer.parseInt(hw.nextToken());
            char [][] map = new char[H+2][W+2];

            for(int i=0; i<H+2; i++){
                Arrays.fill(map[i], '.');
            }
            for(int i=1; i<H+1; i++){
                String input = br.readLine();
                for(int j=1; j<W+1; j++){
                    map[i][j] = input.charAt(j-1);
                }
            }
            String keyList = br.readLine();
            HashSet<Integer> keys = new HashSet<>();
            for(char x: keyList.toCharArray()){
                keys.add(x-'a');
            }
            boolean [][] visited = new boolean[H+2][W+2];
            ArrayDeque <int[]> q = new ArrayDeque<>();
            visited[0][0] = true;
            int dollar = 0;
            q.add(new int[]{0,0});
            while(!q.isEmpty()){
                int [] cur = q.poll();
                int x = cur[0];
                int y = cur[1];
                if(map[x][y]>='A'&&map[x][y]<='Z'&&!keys.contains(map[x][y]-'A')){//열쇠없는 문에 도달
                    continue;
                }
                else if(map[x][y]>='a'&&map[x][y]<='z'&&!keys.contains(map[x][y]-'a')){//새로운 열쇠
                    keys.add(map[x][y]-'a');
                    map[x][y]='.';
                    visited = new boolean [H+2][W+2];
                    q.add(new int[]{0,0});
                    visited[0][0]= true;
                    continue;
                }
                else if(map[x][y]=='$'){
                    dollar++;
                    map[x][y]='.';
                }
                for(int i=0; i<4; i++){
                    int mx = x+ dx[i];
                    int my = y+ dy[i];
                    if(canGo(mx, my)&&!visited[mx][my]&& map[x][y]!='*'){
                        visited[mx][my] = true;
                        q.add(new int []{mx, my});
                    }
                }
            }
            sb.append(dollar).append("\n");
        }
        System.out.print(sb);
    }
    static boolean canGo(int x, int y){
        return x>=0&&y>=0&&x<H+2&&y<W+2;
    }
}

성공~