[백준] 9328 열쇠

문제보기

이거 처음 인강으로 봤을땐 절대 못풀거라고 생각해서 바로 패스했던건데

다시 보니까 생각보다 빨리 풀 수 있었다 헤헤

큐 : 이 자리에 나의 분신을 놓고 간다 -> 라고 생각하면 금방 풀이가 떠오를 것!

import java.util.*;
import java.io.*;
class Pair{ // 위치를 표시할 클래스 
  int x;
  int y;
  Pair(int x, int y){
    this.x = x;
    this.y = y;
  }
}
public class Main{
  static int h; 
  static int w;
  static String ABC; // 대문자 알파벳 모음
  static String abc; // 소문자 알파벳 모음 
  static String key; // 내가 소유한 키 
  static char[][] map; // 주어진 맵
  static boolean[][] check; // 방문 여부 
  static int[] dx = {1, -1, 0, 0}; // 상하좌우
  static int[] dy = {0, 0, 1, -1};

  static void bfs(int a, int b){
    Queue<Pair> q = new LinkedList<>();
    q.add(new Pair(a, b));
    check[a][b] = true;
    int doc = 0; // 훔친 문서의 갯수 
    // 아직 못 연 문 대기열
    ArrayList<Pair>[] wait = (ArrayList<Pair>[]) new ArrayList[26]; 
    for(int i = 0 ; i < 26 ; i++ ){ 
      wait[i] = new ArrayList<Pair>();
    }

    while(!q.isEmpty()){
      Pair p = q.remove();
      int x = p.x;
      int y = p.y;

      for(int k = 0 ; k < 4 ; k++ ){
        int nx = x + dx[k];
        int ny = y + dy[k];
				// 다음 칸 진행 조건 : 맵에 존재할것 & 벽이 아닐 것 & 방문한 적 없을 것 
        if( nx >= 0 && ny >= 0 && nx < h+2 && ny < w+2 && map[nx][ny] != '*' && check[nx][ny] == false){          
          char c = map[nx][ny]; // 다음 칸의 문자 
          if(ABC.indexOf(c) != -1){ // 가 만약 대문자라면 (문)

            if(key.indexOf(c) != -1){ // 키가 있으면 
              check[nx][ny] = true; // 갈 수 있다
              q.add(new Pair(nx, ny));
            }else{ // 키가 없으면 
              wait[c-'A'].add(new Pair(nx, ny)); // 대기열에 좌표 넣어두자 
            }

          }else if(abc.indexOf(c) != -1 ){ // 다음 칸의 문자가 소문자라면 (열쇠)
            char kk = (char)((int)c - ('a'-'A')); // to Upper Case
            key += kk; // 열쇠 보관함에 추가 
            check[nx][ny] = true; // 갈 수 있다
            q.add(new Pair(nx, ny));

            // get wait list // 해당 키로 열 수 있는 문이 있는지 확인 
            int idx = kk-'A';
            for(int i = 0 ; i < wait[idx].size() ; i++){
              int xx = wait[idx].get(i).x;
              int yy = wait[idx].get(i).y;

              if(check[xx][yy] == false){ // 있다면 방문해주자 
                check[xx][yy] = true;
                q.add(new Pair(xx, yy)); 
              }
            }
            wait[idx] = new ArrayList<Pair>(); // 이미 방문했으므로 비워주자
          }else if(c == '$'){ // 만약 문서라면
            doc++; // 문서 겟!
            check[nx][ny] = true; // 방문하자
            q.add(new Pair(nx, ny));

          }else{ // 그냥 길이라면 
            check[nx][ny] = true; // 가면 된다 
            q.add(new Pair(nx, ny));
          }
        }
      }
    }
    System.out.println(doc); // 탐색이 끝났다면 얻은 문서의 갯수 출력 
  }

  public static void main(String []args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int t = Integer.parseInt(br.readLine());
    ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    abc = ABC.toLowerCase();

    while(t-- > 0){
      StringTokenizer st = new StringTokenizer(br.readLine());
      h = Integer.parseInt(st.nextToken());
      w = Integer.parseInt(st.nextToken());
      map = new char[h+2][w+2]; // 상하좌우로 1칸씩 더 확장하자 (바깥으로도 돌아다닐 수 있으므로)

      for(int i = 1 ; i < h+1 ; i++ ){
        String s = br.readLine();
        for(int j = 1 ; j < w+1 ; j++ ){
          map[i][j] = s.charAt(j-1);
        }
      }
      // 상하좌우 여백에 길 추가하기
      for(int j = 0 ; j < w+2 ; j++ ){
        map[0][j] = '.';
        map[h+1][j] = '.';
      }
      for(int i = 0 ; i < h+2 ; i++ ){
        map[i][0] = '.';
        map[i][w+1] = '.';
      }
      // 키는 모두 대문자로 저장한다 
      key = br.readLine().toUpperCase();
      // 방문 여부 초기화
      check = new boolean[h+2][w+2];
      bfs(0, 0); // 출발지에 대한 언급이 없으므로 그냥 (0,0)으로 줬다 
    }
  }
}