[백준 9328] 열쇠 -JAVA //le_effort//

여러가지 아이디어가 필요한 문제였다

 

핵심 아이디어는 열쇠와 벽을 처리 해주는 것 인데

대문자로 이루어진 문은 소문자로 이루어진 열쇠가 있어야 지나 갈 수 있다

하지만 이런 경우 에는 어떻게 할 까?

 

......

.A..a

*$***

 

이 경우 일반적인 bfs 탐색을 0,0 부터 진행 할 시

A가 a보다 먼저 탐색이 진행된다

하지만 a 열쇠가 접근 할 수 있는 곳에 있으니 저 A문을 열 수 있어야 한다.

 

이는 열쇠가 없어서 못여는 문이 있을경우 일단 리스트에 넣어놓는 것 이다.

 

나는 열쇠와 문을 아스키 코드로 처리를 했는데

알파벳은 대소문자를 떠나서 A~Z 총 25개가 있다.

int tmp = 'A'-'A'  =0;

int tmp = 'B'-'A" =1;

int tmp = 'C'-'A' =2;

즉  비교대상 -'A' 가 0~25 사이면 대문자 비교대상 -'a' 가 0~25 사이면 소문자다

 

그리고 예를들어 문 A가 있다 했을때

맵에 A 가 여러개 있을 수 있으므로 리스트에 좌표를 담아줬다 이는 코드 주석설명에 있으니 참고하길 바란다.

 

맵을 왜 [h+2][w+2] 크기로 했는지 궁금한 사람은 

https://suhyeokeee.tistory.com/13?category=837216

[백준 9376] 탈옥 -JAVA // le_effort//

여길 참고하면 될 것 같다.

import java.io.*;
import java.util.*;
public class Main {
    static int t,h,w;
    static boolean visited[][];
    static Character map [][];
    static ArrayList<Node>[]gate;
    static boolean key[];
    static int cnt =0;
    static int dx[] = {0,0,1,-1};
    static int dy[] = {1,-1,0,0};
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t = Integer.parseInt(br.readLine());
        
        while(t-- >0) {
            String[] input = br.readLine().split(" ");
            h = Integer.parseInt(input[0]);
            w = Integer.parseInt(input[1]);
            
            cnt=0;
            map = new Character[h+2][w+2];
            visited = new boolean[h+2][w+2];
            key = new boolean[26];
            
            gate = new ArrayList[26];
            //gate 크기가 26인 이유 A~Z가 25개니 이렇게 두고
            // A열쇠를 가지고 있는 좌표가 여러개 있을 수 있으니 gate[0] = (1,2) //( 2,3) 0 은 A를 뜻한다   
            for(int i=0; i<26; i++) {
                gate[i] = new ArrayList<>();
            }
            for(int i=0; i<h+2; i++) {
                for(int j=0; j<w+2; j++) {
                    map[i][j]='.';
                }
            }
            
            for(int i=1; i<=h; i++) {
                String str = br.readLine();
                for(int j=1; j<=w; j++) {
                    map[i][j] = str.charAt(j-1);
                }
            }
            String key_input = br.readLine();
            if(!key_input.equals("0")) {
                for(int i=0; i<key_input.length(); i++) {
                    int tmp = key_input.charAt(i) -'a';
                    key[tmp] = true;
                }
            }
            bfs();
            System.out.println(cnt);
            
        }
    }
    public static void bfs() {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(0,0));
        visited[0][0] = true;
        
        while(!q.isEmpty()) {
            Node a = q.poll();
            for(int i=0; i<4; i++) {
                int nx = a.x+dx[i];
                int ny = a.y+dy[i];
                if(nx>=0 && ny>=0 && nx<h+2 && ny<w+2) {
                    if(!visited[nx][ny] && map[nx][ny]!='*') {
                        if(map[nx][ny]-'A'>=0 && map[nx][ny]-'A'<=25) {    // 알파벳 대문자를 아스키코드로 구해줌
                            if(key[map[nx][ny]-'A']) {    // 아스키코드로 열쇠를 가지고 있는지 체크
                                map[nx][ny]='.';    // 문을 열어줌
                                q.add(new Node(nx,ny));
                                visited[nx][ny]=true;
                            }
                            else {
                                // 해당하는 열쇠가 없을경우 뒤에서 열쇠가 발견 될 수 있으니 일단 gate에 넣어줌 
                                gate[map[nx][ny]-'A'].add(new Node(nx,ny));
                            }
                        }
                        else if(map[nx][ny]-'a'>=0 && map[nx][ny]-'a'<=25) {    // 아스키코드로 열쇠를 넣어줌
                            key[map[nx][ny]-'a'] = true;
                            visited[nx][ny] = true;
                            q.add(new Node(nx,ny));
                        }
                        else if(map[nx][ny] == '.') {    //빈칸 인 경우 진행
                            visited[nx][ny] = true;    
                            q.add(new Node(nx,ny));
                        }
                        else if(map[nx][ny]=='$') {    //문서 발견시 cnt ++
                            cnt++;
                            visited[nx][ny] = true;
                            q.add(new Node(nx,ny));
                        }
                        
                        for(int j=0; j<=25; j++) {
                            if(gate[j].size()!=0 && key[j]) {
                                for(int k=0; k<gate[j].size(); k++) {
                                    Node tmp= gate[j].get(k);
                                    map[tmp.x][tmp.y] ='.';
                                    visited[tmp.x][tmp.y] = true;
                                    q.add(new Node(tmp.x,tmp.y));
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}
 
class Node{
    int x,y;
    Node(int x, int y){
        this.x=x;
        this.y=y;
    }
}