[BOJ] 1194 달이 차오른다, 가자. (Java)

1. 문제 링크

https://www.acmicpc.net/problem/1194

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

 

2. 접근법

탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 문제이므로 BFS 탐색을 하자

획득한 열쇠의 경우의 수에 따라서 방문 처리를 다르게 해줘야 함

 

그렇다면 어떻게 획득한 열쇠를 저장할 것인지, 방문 처리를 어떻게 할 것인지 가 포인트

비트마스킹을 활용하자!

 

1. 변수 선언

열쇠는 A부터 F까지 총 6 종류이므로 2^6의 경우의 수가 생김

Point 클래스의 keyInfo 속성을 int 타입으로 선언, 6자리의 비트로 저장함

 

visited 배열은 3차원으로 선언, visited[n][n][1 << 6] 으로 세번째 자리에 획득한 열쇠에 따라 방문 여부를 저장해줌

 

2. BFS 탐색

일반적인 BFS 탐색 문제처럼 똑같이 진행함

출구인 1을 만나면 리턴

문을 만나면, 현재 keyInfo에 해당하는 문의 열쇠가 담겨있는지 판단하기, 그리고 queue에 넣어 탐색 이어가기

열쇠를 만나면, 현재 keyInfo에 해당 열쇠를 담기, 그리고 queue에 넣어 탐색 이어가기

빈 칸이라면, queue에 넣어 탐색 이어가기

 

 while문 내에서 1을 만나지 못했다면 출구를 찾지 못했다는 의미이므로 -1 리턴

 

3. 코드

import java.io.*;
import java.util.*;

// 달이 차오른다, 가자.

public class BJ1194 {

   static class Point {
	   int x;
	   int y;
	   int cnt;
	   int keyInfo;

	   Point(int x, int y, int cnt, int keyInfo) {
		   this.x = x;
		   this.y = y;
		   this.cnt = cnt;
		   this.keyInfo = keyInfo;
	   }
   }
   static int n, m;
   static char[][] map;
   static boolean[][][] visited;
   static ArrayDeque<Point> queue = new ArrayDeque<>();
   static int[] dx = {-1, 0, 1, 0};
   static int[] dy = {0, 1, 0, -1};

   public static void main(String[] args) throws Exception {

	   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][1 << 6];

	   for(int i = 0; i < n; i++) {
		   String line = br.readLine();
		   for(int j = 0; j < m; j++) {
			   map[i][j] = line.charAt(j);
			   if(map[i][j] == '0') {
				   visited[i][j][0] = true;
				   queue.add(new Point(i, j, 0, 0));
				   map[i][j] = '.';
			   }
		   }
	   }

	   System.out.println(bfs());
   }

   private static int bfs() {

	   while(!queue.isEmpty()) {
		   Point poll = queue.poll();

		   for(int i = 0; i < 4; i++) {
			   int xx = poll.x + dx[i];
			   int yy = poll.y + dy[i];

			   if(xx < 0 || xx >= n || yy < 0 || yy >= m || map[xx][yy] == '#' || visited[xx][yy][poll.keyInfo]) continue;
			   if(map[xx][yy] == '1') {
				   return poll.cnt + 1;
			   }

			   if('A' <= map[xx][yy] && map[xx][yy] <= 'F') {
				   if((poll.keyInfo & (1 << (map[xx][yy] - 65))) != 0) {
					   visited[xx][yy][poll.keyInfo] = true;
					   queue.add(new Point(xx, yy, poll.cnt + 1, poll.keyInfo));
				   }
			   }
			   else if('a' <= map[xx][yy] && map[xx][yy] <= 'f') {
				   int newKeyInfo = poll.keyInfo | (1 << (map[xx][yy] - 97));
				   visited[xx][yy][newKeyInfo] = true;
				   queue.add(new Point(xx, yy, poll.cnt + 1, newKeyInfo));
			   }
			   else {
				   visited[xx][yy][poll.keyInfo] = true;
				   queue.add(new Point(xx, yy, poll.cnt + 1, poll.keyInfo));
			   }
		   }
	   }

	   return -1;
   }
}

 

4. 막힌 부분

역시나 비트마스킹을 활용할 생각을 못했다...

 

처음에는 열쇠를 HashSet에 저장하고

visited 배열은 2차원으로 선언 후 Point 클래스에 visited 배열을 담아야하나..?

획득한 열쇠마다 방문한 경로가 다를텐데 어떻게 처리하지... 의문이었다.

 

더 깊게 생각 못하고 수업시간에 풀이를 들었다.

듣고 유사하게 풀었던 풀이가 생각났고 바로 적용해서 풀었다.

 

약 열흘만에 다시 문제를 풀기 시작했는데 음... 괜히 감 떨어진 느낌?ㅠ

탐색에서 3차원 배열 활용하는 부분을 더 봐야겠다.