백준 1194 <달이 차오른다,가자>

우선 문제에서 이동 횟수의 최솟값을 구하라고 했기 때문에 BFS를 이용해야 하는 문제이다.

 

그리고 한가지 더 주의해야 할 점은 각각의 이동 시마다 가지고 있는 키를 알고 있어야 하는 문제이다.

 

각각의 가지고 있는 키의 정보를 저장하기 위해 key[] 배열을 가지고 있어도 되지만 크기를 줄이기 위해 비트 연산을 사용하도록 하는 문제이다. 비트 연산을 알지 못하면 어려운 문제이다.

 

 

전체적인 맵에서 각각의 키를 가지고 있는지 표시하기위해 1<<6을 나타내서 2의 6승까지 배열을 만들어주었다.

 

이렇게 해 준 이유는 

BFS에 현재 가지고 있는 KEY도 넣어주기 위해 flag 라는 int형을 선언하고 x, y는 각각의 좌표와 cnt는 총 이동 수이다.

 

이는 현재 가지고 있는 KEY를 이용해 BFS를 하는 코드이다 

이 코드에서 가장 유의 깊게 봐야하는 코드는 두 가지이다.

 

1. 다음 이동할 위치가 key가 있는 위치인 가이다.

이곳을 방문하지 않았다면  현재의 flag | ( 1 << 현재 위치의 키- 'a' ) 이렇게 해서 큐에 추가해준다.

현재위치의 키- 'a' 이렇게 해주는 이유는 알파벳에 따라 a-'a'=0 이기 때문에 0번째 자리를 바꿔준다는 것이다.

 

2. 다음 이동할 자리가 문이면 현재 문에 해당하는 키를 가지고 있는지 확인하는 것이다.

 

현재 이동할 위치가 문일 경우 flag & ( 1 << 현재 위치의 키- 'a' ) 이렇게 해서 0이 아니라면 키를 가지고 있다는 뜻이니 문에 접근할 수 있고 queue에 추가할 수 있게 된다.

 

이렇게 계속적으로 검사를 해주게 되고 큐에서 꺼낸값이 1이 위치 한자리면 꺼낸값의 이동거리를 결과로 넣어주고 return 시킨다.

 

전체 코드

import java.util.*;

public class Main{

	public static class move{
		int x;
		int y;
		int flag;
		int cnt;
		public move(int x, int y, int flag, int cnt) {
			super();
			this.x = x;
			this.y = y;
			this.flag = flag;
			this.cnt = cnt;
		}
		
	}
	static String map[];
	static int n,m,result=-1,visit[][][],dir[][]= {{-1,0},{0,1},{1,0},{0,-1}},sx,sy;
	static Queue<move> q=new LinkedList<move>();
			
   public static void main(String[] args) {
      Scanner kb = new Scanner(System.in);
      n=kb.nextInt();
      m=kb.nextInt();
      map=new String[n];
      visit=new int[n][m][1<<6];
      for(int i=0;i<n;i++) {
    	  map[i]=kb.next();
    	  for(int j=0;j<m;j++) {
    		  if(map[i].charAt(j)=='0') {
    			  sx=i;
    			  sy=j;
    		  }
    	  }
      }
      visit[sx][sy][0]=1;
      q.add(new move(sx,sy,0,0));
      bfs();
      System.out.println(result);
      
   }
   public static void bfs() {
	   while(!q.isEmpty()) {
		   move next=q.remove();
		   if(map[next.x].charAt(next.y)=='1') {
			   result=next.cnt;
			   break;
		   }
		   for(int i=0;i<4;i++) {
			   int x1=next.x+dir[i][0];
			   int y1=next.y+dir[i][1];
			   if(x1>=0&&x1<n&&y1>=0&&y1<m&&map[x1].charAt(y1)!='#'
                  &&visit[x1][y1][next.flag]==0) {
				   if(map[x1].charAt(y1)>='a'&&map[x1].charAt(y1)<='f') {
					   q.add(new move(x1,y1,next.flag|(1<<(map[x1].charAt(y1)-'a')),next.cnt+1));
					   visit[x1][y1][next.flag]=1;
				   }
				   else if(map[x1].charAt(y1)>='A'&&map[x1].charAt(y1)<='F') {
					   if((next.flag&(1<<(map[x1].charAt(y1)-'A')))!=0) {
						   q.add(new move(x1,y1,next.flag,next.cnt+1));
						   visit[x1][y1][next.flag]=1;
						   //System.out.println(next.cnt);
					   }
				   }
				   else {
					   q.add(new move(x1,y1,next.flag,next.cnt+1));
					   visit[x1][y1][next.flag]=1;
				   }
			   }
		   }
	   }
   }

   
}