[ 백준 ] [ 자바 ][ 1194] 달이 차오른다 가자

이제 조금 3차원 방문배열을 이해 할랑 말랑 싶다

처음에 키값이 있는지 없는지 확인하려면 그냥 map이나 또는 

링크드 리스트에 넣어서 루프돌려서 확인하면 되지 않을까? 

라고 생각해서 풀었는데 

 

각 키를 주웠을떄의 상황을 생각해보자면 3차원 배열을 만드는게 가장 효율적인것 같다

비트마스킹은 의외로 간단하다

이진수를 생각하자면 

1과 0으로 나누어져있는데

key 값 

abcdef 를 각각 전구 처럼 생각하면 쉽다

a를 방문했을떄 a 전구를 키고 

b를 방문했을떄 b전구를 키는 식으로 생각하는 것이다.

 

모든 키값은 interger 하나로  가능해진다 즉 

비트마스킹을 이용하면 3차원 배열로 해결이 가능해진다. 

 

열쇠 문제랑 유사한데 

..운이 좋아서 풀린거였다.

 

예전에는 이해가 아예 되지도 않았는데 이제 살짝 마음으로는 이해할랑 말랑 싶다

다른 문제도 건드려 봐야겠다.

package back;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Tile{
   int y;
   int x;
   int key;
   Tile(int y, int x, int key ) {
      this.y = y;
      this.x = x;
      this.key = key;
   }
}
//
//5 5
//....1
//#1###
//.1.#0
//....A
//.1.#.
public class Main_backjoon_1194_달이차오른다가자 {
   static char[][] MAP;
   static boolean[][][] VISITED;
   static int[] dx = {1,-1,0,0} ;
   static int[] dy = {0,0,1,-1}; 
   static int N;
   static int M;
   static LinkedList keyList;
   static int startX;
   static int startY;
   static Queue q;
   public static void main(String[] args) throws IOException {
      BufferedReader  br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine(), " ");
      N = Integer.parseInt(st.nextToken());
      M = Integer.parseInt(st.nextToken());   
      MAP = new char[N][M];
      VISITED = new boolean[N][M][101];
      q = new LinkedList();
      keyList = new LinkedList();
      for(int i= 0; i < N ;i++) {
         char[] array = br.readLine().toCharArray();
         for(int j = 0; j < M ;j++) {
            MAP[i][j] = array[j];
            if(MAP[i][j] == '0' ) { 
               startY = i;
               startX = j;
            }
         }
      }
      q.add(new Tile(startY, startX, 0 ));
      VISITED[startY][startX][0] = true;
      MAP[startY][startX] = '.';
      bfs();
   }
   public static void bfs() {
      int distance = 0;
      boolean flag = false;
      while(!q.isEmpty()) {
         int qsize = q.size();
         for(int s = 0; s < qsize; s++) {
        	Tile p =  q.poll();
        	if(MAP[p.y][p.x] == '1') {
        		System.out.println(distance);
        		return;
        	}
            for(int d = 0; d < 4; d++ ) {
               int yy = dy[d] + p.y;
               int xx = dx[d] + p.x; 
               int key = p.key;
               
               if(!isRange(yy, xx)) {
                  continue;
               }           
               if( MAP[yy][xx] == '#') {
            	   continue;
               }
               if(VISITED[yy][xx][key]) {
                  continue;
               }
               
               //System.out.println("KEY " + key  +" " + yy + " " + xx );
               //빈 공간 
               if(MAP[yy][xx] == '1') {
            	   q.add(new Tile(yy, xx, key ));
            	   VISITED[yy][xx][key] = true;
            	   continue;
               }
               if( MAP[yy][xx] == '.' ) {
                  q.add(new Tile(yy, xx, key ));
                  VISITED[yy][xx][key] = true;
               }
               //소문자 일경우 
               if(Character.isLowerCase(MAP[yy][xx])) {
            	   //key를 넣어야함 
            	   key |= 1 << MAP[yy][xx] - 'a';
            	   //System.out.println("lower " +  MAP[yy][xx] + " " + key);
            	   q.add(new Tile(yy, xx, key));
            	   VISITED[yy][xx][key] = true;	   
               }
               //대문자일 경우 
               if( Character.isUpperCase(MAP[yy][xx]) ) {
            	   //현재 key가 있는지 확인 할 것 
            	   //AND 연산자는 둘다 있어야 1 
            	   //System.out.println("Uppercase MAP[yy][xx]" + MAP[yy][xx]  + (key & 1 << MAP[yy][xx] - 'A'));
            	   if( ( key & 1 << MAP[yy][xx] - 'A' ) != 0) {
            		   //있으면 다음 블록 추가 
            	        q.add(new Tile(yy, xx, key ));
            	        VISITED[yy][xx][key] = true;	   
            	   }
               }
            }
         }
         distance += 1;
      }
      System.out.println("-1");
   }
   //대문자일경우 현재 문을 열 수 있는지 없는 지를  검사 해야함 
   public static boolean isRange(int yy, int xx) {
      if( yy >= 0 && yy < N && xx >= 0 && xx < M) {
         return true;
      }else {
         return false;
      }
   }
}