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

1. 문제 링크

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

 

2. 문제 및 입출력예제

 

3. 문제 풀이

비트마스킹을 해야 하는 문제라 조금 어려웠다.

시작점부터 BFS 하면서 해당 위치가 벽/열쇠/문/출구인지에 따라 다른 조건문에 들어간다.

출구가 나오면 최댓값을 갱신하고 return한다.

빈 칸인 경우에는 갈 수 있는 곳이므로 queue에 넣는다.

열쇠가 나올 경우 비스마스킹으로 키를 추가하고 갈 수 있는 곳이므로 queue에 넣는다.

대문자일 경우 해당 문자열을 키가 가지고 있는지 판단한다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
	static class Point{
		int x;
		int y;
		int time;
		int key;
		public Point(int x, int y, int time, int key) {
			super();
			this.x = x;
			this.y = y;
			this.time = time;
			this.key = key;
		}
	}
	static int[] dx = {0,0,1,-1};
	static int[] dy = {1,-1,0,0};
	static int result, N, M;
	static char[][] map;
	static boolean[][][] visit;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		result = Integer.MAX_VALUE;
		String[] split = br.readLine().split(" ");
		N = Integer.parseInt(split[0]);
		M = Integer.parseInt(split[1]);
		map = new char[N][M];
		visit = new boolean[N][M][64];
		
		int startX = 0;
		int startY = 0;
		for(int i=0;i<N;i++) {
			String str = br.readLine();
			for(int j=0;j<M;j++) {
				char temp = str.charAt(j);
				map[i][j] = temp;
				if(temp == '0') { //입구	
					startX = i;
					startY = j;
					map[i][j] = '.';
				}
			}
		} //입력 끝
		
		bfs(startX, startY);
		
		System.out.println(result);
	}
	private static void bfs(int i, int j) {
		Queue<Point> queue = new ArrayDeque<>();
		queue.offer(new Point(i, j, 0, 0));
		visit[i][j][0] = true;
		while(!queue.isEmpty()) {
			Point now = queue.poll();
			int x = now.x;
			int y = now.y;
			int temp = now.time;
			int key = now.key;
			for(int d=0;d<4;d++) {
				int X = x+dx[d];
				int Y = y+dy[d];
				if(X<0 || X>=N || Y<0 || Y>=M || map[X][Y] =='#' || visit[X][Y][key]) {
					continue;
				}

				if(map[X][Y] == '1') {
					result = Math.min(result, temp+1);
					return;
				}
				else if(map[X][Y] =='.') {
					visit[X][Y][key] = true;
					queue.offer(new Point(X, Y, temp+1, key));
				}
				else if(map[X][Y]>='a' && map[X][Y]<='z') { //소문자
					int newKey = 1<< (map[X][Y]-'a');
					newKey = newKey|key;
					if(!visit[X][Y][newKey]) {
						visit[X][Y][key] = true;
						visit[X][Y][newKey] = true;
						queue.offer(new Point(X, Y, temp+1, newKey));
					}
				}
				else if(map[X][Y]>='A' && map[X][Y]<='Z') { //대문자
					if((key & (1<<map[X][Y]-'A')) >0) {
						visit[X][Y][key] = true;
						queue.offer(new Point(X, Y, temp+1, key));
					}
				}
			}
		}
		result = -1;
	}
}