[BOJ] 1194 달이 차오른다, 가자 - JAVA

1. 문제

1194번: 달이 차오른다, 가자.

지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.

민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.

하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.

영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.

민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.

• 빈 칸: 언제나 이동할 수 있다. ('.')
• 벽: 절대 이동할 수 없다. ('#')
• 열쇠: 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. ('a', 'b', 'c', 'd', 'e', 'f')
• 문: 대응하는 열쇠가 있을 때만 이동할 수 있다. ('A', 'B', 'C', 'D', 'E', 'F')
• 민식이의 현재 위치: 빈 곳이고, 민식이가 현재 서 있는 곳이다. ('0')
• 출구: 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. ('1')

달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.

민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

---

2. 풀이

클래스

• BFS에서 큐에 한번에 집어넣기 위해 클래스를 만들었다. 위치정보와 그 때의 키정보를 담고 있다.

private static class Status{
   int r,c,k;

   private Status(int r,int c,int k){
      this.r = r;
      this.c = c;
      this.k = k;
   }
}

 

입력

• 처음 시작 위치가 주어지지 않기 때문에 입력받으면서 위치를 미리 저장해둔다.
• 방문배열은 3차원인데, 열쇠가 6종류 있기 때문에 111111(2) 총 64가지 경우가 필요하기 때문이다.
• 1번 열쇠가 있다면 000001, 1번 3번 열쇠가 있다면 000101이다. 10진법으로 표현하면 1과 5다.

BufferedReader in =new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(in.readLine());
int[][] deltas = {{1,0},{-1,0},{0,1},{0,-1}};

int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());

char[][] maze = new char[N][M];
Status pos = null;
int[][][] visited = new int[N][M][1<<6];

for(int i=0;i<N;i++) {
   String line = in.readLine();
   for(int j=0;j<M;j++){
      char now = line.charAt(j);
      if(now=='0') pos = new Status(i,j,0);
      maze[i][j] = line.charAt(j);
   }
}

 

BFS(feat. 비트마스크)

• 큐에 초기위치를 넣고, 방문배열에 1을 넣는다. 방문여부도 구분하면서 depth도 체크하기 위해서다. 그래서 마지막에 출력할 때 그 값에 -1을 한다.
• 사방탐색을 하면서 다음의 경우를 제외한다.
  
  1. 범위에 벗어난 경우
  2. 벽인 경우
  3. 문인데 열쇠가 없는 경우 ( pos.k & 1<<(next-'A')==0 : &연산결과가 0이라면 뽑힌 적이 없는 것이다)
  4. 이미 방문한 적이 있는 경우
• next가 열쇠라면 1<<(next-'a')값과 pos.k값을 |연산해서 그 자리가 1이 되도록 다음 키값(nk)을 만든다.  
• pos값에 +1을 해서 새 위치에 넣는다.
• 큐에도 새 위치를 추가한다.

Queue<Status> queue = new ArrayDeque<>();
queue.offer(pos);
visited[pos.r][pos.c][0] = 1;

while(!queue.isEmpty()){
   pos = queue.poll();
   if(maze[pos.r][pos.c]=='1') {
      System.out.println(visited[pos.r][pos.c][pos.k]-1);
      return;
   }

   for(int d=0;d<4;d++){
      int nr = pos.r+deltas[d][0];
      int nc = pos.c+deltas[d][1];
      if(nr<0 || nr>=N || nc<0 || nc>=M) continue;
      int next = maze[nr][nc];
      if(next=='#') continue;
      if(next>='A' && next<='F' && (pos.k&1<<(next-'A'))==0) continue;
      int nk = next>='a' && next<='f'? pos.k|1<<(next-'a'):pos.k;
      if(visited[nr][nc][nk]!=0) continue;
      visited[nr][nc][nk] = visited[pos.r][pos.c][pos.k]+1;
      queue.offer(new Status(nr,nc,nk));
   }
}

System.out.println(-1);

---

3. 결과

비트마스킹을 생각해내기까지가 오래걸렸던 문제였다.