링크

문제 링크

문제 설명

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

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

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

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

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

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

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

입력

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 문에 대응하는 열쇠가 없을 수도 있다. '0'은 한 개, '1'은 적어도 한 개 있다. 열쇠는 여러 번 사용할 수 있다.

출력

첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.

입출력 예제

풀이

1. 기본적인 유형은 BFS지만, 문에 맞는 열쇠를 구하는 것이 이 문제의 관건이다.
2. 벽 부수고 이동하기 때는 벽을 부순 경험이 있는 채로 그 위치에 방문한 적이 있는가? 가 풀이였는데, 이번에는 지금 가지고 있는 열쇠꾸러미로 그 위치에 방문한 적이 있는지 따져야한다.
3. 그 열쇠 꾸러미를 여섯가지의 비트로 구현할것이다!
4. 우선 소문자(열쇠)를 만난다면 현재 열쇠꾸러미에 or 연산을 해서 그 열쇠를 꾸러미에 추가한다.
5. 대문자를 만난다면 현재 열쇠꾸러미에 and 연산을 해서 만약 1이면 해당 문을 열 수 있는 것이다. 0이면 그 열쇠가 없으므로 더이상 전진 X
6. 이렇게 가다가 1 만나면 depth 리턴

음 벽부수고 이동하기를 하고나서 해당 유형에는 이론이 빠삭하다고 생각해서 덤볐지만

비트마스킹을 구현하지 못해서 처음에 해시맵을 쓰거나 좀 난리가 났었다.

블로그에서 비트마스킹이라는 힌트를 얻자마자 여자친구하고 등산을 다녀오고난 오늘 바로 풀었다!

참고로 등산하다가 죽을뻔했다 ㅋㅋ 앞산인데..

코드

import java.util.*;

class PointM {
	int x, y;
	int level;
	int haskey;

	PointM(int x, int y, int level, int haskey) {
		this.x = x;
		this.y = y;
		this.level = level;
		this.haskey = haskey;
	}
}

public class Main {
	static char[][] map;
	static boolean[][][] visited;
	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };
	static char[] keylist = { 'a', 'b', 'c', 'd', 'e', 'f' };
	static char[] doorlist = { 'A', 'B', 'C', 'D', 'E', 'F' };

	public static int index_of_key(char key) {
		for (int i = 0; i < 6; i++)
			if (key == keylist[i])
				return i;
		return -1;
	}

	public static int index_of_door(char key) {
		for (int i = 0; i < 6; i++)
			if (key == doorlist[i])
				return i;
		return -1;
	}

	public static int bfs(PointM start, int N, int M) {
		Queue<PointM> q = new LinkedList<>();
		q.add(start);
		visited[start.x][start.y][0] = true;
		
		while (!q.isEmpty()) {
			PointM p = q.poll();
			for (int i = 0; i < 4; i++) {
				int nx = p.x + dx[i];
				int ny = p.y + dy[i];
				if (nx < 0 || nx >= N || ny < 0 || ny >= M) // out of range
					continue;
				if(map[nx][ny] == '1')
					return p.level + 1;
				if (map[nx][ny] != '#' && !visited[nx][ny][p.haskey]) {
					if (map[nx][ny] == '.') { // 그 키를 들고 방문한 적 없는 경우
						q.add(new PointM(nx, ny, p.level + 1, p.haskey));
						visited[nx][ny][p.haskey] = true;
					} else if (index_of_key(map[nx][ny]) > -1) { // key 만났을 떄
						q.add(new PointM(nx, ny, p.level + 1, p.haskey | (32 >> index_of_key(map[nx][ny]))));
						visited[nx][ny][p.haskey] = true;
					} else if (index_of_door(map[nx][ny]) > -1) { // door 만났을 때
						int temp = p.haskey & (32 >> index_of_door(map[nx][ny]));
						if (temp == 0)
							continue;
						q.add(new PointM(nx, ny, p.level + 1, p.haskey));
						visited[nx][ny][p.haskey] = true;
					}
				}
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		map = new char[N][M];
		visited = new boolean[N][M][64];

		PointM start = null;
		for (int i = 0; i < N; i++) {
			String s = sc.next();
			map[i] = s.toCharArray();
			for (int j = 0; j < map[i].length; j++) {
				if (map[i][j] == '0') {
					start = new PointM(i, j, 0, 0);
					map[i][j] = '.';
				}
			}
		}
		System.out.println(bfs(start, N, M));
	}
}