BOJ 백준온라인져지 1194 달이 차오른다, 가자. 풀이

1. 비트마스크 문제

2. 1 << 6 를 하면 6자리 비트가 생긴다.

3. 그 비트로 a~f 의 열쇠가 있는지 검사하고, 찾으면 넣는다.

4. visited 에는 위치, 보유한 열쇠의 이동거리값이 들어있다.

	import java.util.*;
	import java.io.*;
	/**
	* https://www.acmicpc.net/problem/1194
	* BOJ 백준온라인져지 1194 달이 차오른다, 가자. 풀이
	*/
	public class Main {
	static class State {
	public int x, y, z;
	public State (int x, int y, int z) {
	this.x = x;
	this.y = y;
	this.z = z;
	}
	}
	private static int xxxx[] = { 0, -1, 0, 1 };
	private static int yyyy[] = { -1, 0, 1, 0 };
	private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static void main (String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	String str1[] = br.readLine().split(" ");
	int N = Integer.parseInt(str1[0]);
	int M = Integer.parseInt(str1[1]);
	char map[][] = new char[N][M];
	Queue<State> q = new LinkedList<>();
	for (int i = 0; i < N; i++) {
	String str2[] = br.readLine().split("");
	for (int j = 0; j < M; j++) {
	map[i][j] = str2[j].charAt(0);
	if (map[i][j] == '0') {
	q.offer(new State(i, j, 0));
	}
	}
	}
	int visited[][][] = new int[N][M][1 << 6];
	while (q.size() > 0) {
	State state = q.poll();
	int preX = state.x;
	int preY = state.y;
	int z = state.z;
	if (map[preX][preY] == '1') {
	System.out.println(visited[preX][preY][z]);
	return;
	}
	for (int i = 0; i < 4; i++) {
	int curX = preX + xxxx[i];
	int curY = preY + yyyy[i];
	if (curX < 0 || curY < 0 || curX >= N || curY >= M || visited[curX][curY][z] > 0 || map[curX][curY] == '#') continue;
	if (map[curX][curY] >= 'a' && map[curX][curY] <= 'f') {
	int curZ = z | (1 << map[curX][curY] - 'a');
	visited[curX][curY][curZ] = visited[preX][preY][z] + 1;
	q.offer(new State(curX, curY, curZ));
	} else if (map[curX][curY] >= 'A' && map[curX][curY] <= 'F') {
	if (((1 << map[curX][curY] - 'A') & z) > 0) {
	visited[curX][curY][z] = visited[preX][preY][z] + 1;
	q.offer(new State(curX, curY, z));
	}
	} else {
	visited[curX][curY][z] = visited[preX][preY][z] + 1;
	q.offer(new State(curX, curY, z));
	}
	}
	}
	bw.write("-1");
	bw.flush();
	}
	}

view raw Main.java hosted with ❤ by GitHub

문제

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

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

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

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

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

• 빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨)
• 벽 : 절대 이동할 수 없다. (‘#’)
• 열쇠 : 언제나 이동할 수 있다. 이 곳에 처음 들어가게 되면 열쇠를 집는다. (소문자 a - f)
• 문 : 대응하는 열쇠가 있을 때만 이동할 수 있다. (대문자 a - f)
• 민식이의 현재 위치 : 빈 곳이고, 민식이가 현재 서 있는 곳이다. (숫자 0)
• 출구 : 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. (숫자 1)

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

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

입력

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

출력

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