[JAVA] 백준 1194 : 달이 차오른다, 가자.

문제

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

 

해결방법

방문 체크가 중요한 문제이다.

열쇠가 a ~ f 가 존재하고 각 열쇠에 해당되는 문이 A ~ F가 존재한다.

방문 체크를 열쇠를 아예 들고 있지 않을 때, a만 들고 있을 때, a와 b를 들고 있을 때 등으로 나누어서 체크를 해주어야 한다.

그렇게 하면 총 6개 열쇠를 모두 방문 체크를 해주어야 되기 때문에 좌표값 + 6 해서 8차원 배열을 사용해야 한다.

그래서 비트 마스크를 사용한다.

 

비트마스크를 사용하면 아예 사용하지 않는 경우까지 포함하면 총 7개 즉 2^7 인 128개만 사용하면 된다.

(추 후에 생각해보니, 아예 사용하지 않는 경우는 0번 인덱스를 사용하면 돼서 2^6인 64개로 가능하다.)

그래서 방문 배열을 [row][col][128]로 생성해서 사용했다.

 

큐는 우선순위 큐를 사용해서 가장 먼저 최소 횟수만큼 움직인 경우가 도착하게끔 하였고

바로 break로 큐를 탈출해서 값을 출력하게끔 했다.

만약 목적지에 도달하지 못한다면 처음 초기화되어 있는 값 -1이 출력된다.

 

탐색 중에 열쇠를 만나면 비트 마스크를 사용해서 key를 추가해주었고(a는 한 칸, b는 두 칸 좌측으로 시프트)

문을 만나면 현재 가지고 있는 key가 해당 문을 열 수 있는지 체크해서 있다면 진행하게끔 하였다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		char[][] maze = new char[N][M];
		boolean[][][] visit = new boolean[N][M][128]; //7 
		int startR = 0;
		int startC = 0;
		
		for (int i = 0; i < N; i++) {
			String temp = br.readLine();
			for (int j = 0; j < M; j++) {
				maze[i][j] = temp.charAt(j);
				if (maze[i][j] == '0') {
					startR = i;
					startC = j;
				}
			}
		}
		
		PriorityQueue<Move> q = new PriorityQueue<>();
		q.offer(new Move(startR, startC, 1, 0));
		visit[startR][startC][1] = true;
		int result = -1;
		
		while (!q.isEmpty()) {
			Move move = q.poll();
	
			if (maze[move.r][move.c] == '1') {
				result = move.cnt;
				break;
			}
			
			for (int i = 0; i < 4; i++) {
				int nr = move.r + dr[i];
				int nc = move.c + dc[i];
				
				if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
				
				// 방문하지 않았거나 벽이 아니라면 방문하기
				if (!visit[nr][nc][move.key] && maze[nr][nc] != '#') {
					// 열쇠를 발견했을 때
					if (maze[nr][nc] >= 'a' && maze[nr][nc] <= 'f') {
						int key = move.key | (1 << maze[nr][nc] - 'a' + 1);
						visit[nr][nc][key] = true;
						q.offer(new Move(nr, nc, key, move.cnt + 1));
					
					// 문을 발견했을 때
					} else if (maze[nr][nc] >= 'A' && maze[nr][nc] <= 'F') {
						int flag = 1 << (maze[nr][nc] - 'A' + 1);
						
						// 문을 지나갈 수 있다면
						if ((move.key & flag) == flag) {
							visit[nr][nc][move.key] = true;
							q.offer(new Move(nr, nc, move.key, move.cnt + 1));
						}
					} else {
						visit[nr][nc][move.key] = true;
						q.offer(new Move(nr, nc, move.key, move.cnt + 1));
					}
				}
			}
		}
		System.out.println(result);
	}
	
	static class Move implements Comparable<Move> {
		int r;
		int c;
		int key;
		int cnt;
		
		Move (int r, int c, int key, int cnt) {
			this.r = r;
			this.c = c;
			this.key = key;
			this.cnt = cnt;
		}

		@Override
		public int compareTo(Move o) {
			// TODO Auto-generated method stub
			return cnt - o.cnt;
		}
	}
}