[java] 백준(BOJ) - 달이 차오른다, 가자.

문제

백준-달이 차오른다, 가자.
민식이가 미로를 탈출하는데 걸리는 이동횟수의 최솟값을 구하는 문제

• 제한사항 미로의 세로, 가로크기 N,M : 1 <= N,M <= 50
  문을 열 수 있는 열쇠 : a ~ f
  문 : A ~ F
  벽 : (‘#’) 절대 이동할 수 없음
  민식이의 위치 : (‘0’) 1개 있음
  출구 : (‘1’) 1개 이상 있음
  빈 곳 : (‘.’)
  같은 열쇠가 여러 개 있을 수 있고, 문도 여러 개 있을 수 있다
  한 열쇠로 여러 문을 열 수 있다(여러번 사용할 수 있음)

풀이

비트마스킹에 익숙해지기 위한 문제풀이(bfs와 비트마스킹 사용)
(아직 미숙한 단계 😅😂)
이쯤되면 비트마스킹할때 어떤 것을 상태로 놓을지 감이온다
열쇠와 문이 6개이므로 1 << 6을 해서 열쇠의 보유현황을 사용하기로 했다
열쇠는 소문자로, 문은 대문자로 표시된다

그러므로 열쇠 “a”는 'a' - 97을 해서 0으로,
문 “A”는 'A' - 65를 이용해서 확인한다

예를 들어서, 열쇠 ‘a’,’c’를 가지고 있다고 하자

열쇠를 나타내는 상태 비트의 순서: fedcba
각 열쇠부분이 1이면 보유하고 있음, 0이면 보유하지 않음을 나타낸다
그렇다면 ‘a’를 가진 것은 “000001”로 표현할 수 있다(십진수 : 1)
마찬가지로 ‘a’,’c’를 가지고 있다면 “000101”로 표현할 수 있다(십진수 : 5)

만약에 ‘a’,’c’를 가지고 있는 상태(000101)에서 문”C”를 만났다고 한다면,
문 “C”는 'C'-65를 해서 2을 구한다음, 상태 | (1 << 2)의 결과로 문을 열 수 있는지 판단할 수 있다
0 0 0 1 0 1 (현재 상태)
0 0 0 1 0 0 (1 « 2)
0 0 0 1 0 0 (두 값을 OR(|)한 결과)

0보다 크다는 것은, 열쇠를 가지고 있으며 문을 열 수 있다는 것을 의미한다

bfs로 출발지점에서 시작하는데 Loc클래스를 생성해서 사용했다

class Loc{
	int x; // 좌표
	int y;
	int state; // 열쇠 보유 상태
	int steps; // 이동 칸의 수
}

최솟값을 저장할 변수는 ans = Integer.MAX_VALUE로 초기화했다

방문한 위치를 확인하는 것은 visit[][][]에 기록해서 판별했다
visit[state][x][y]로 각 열쇠보유에 따른 x좌표, y좌표로 기록했다

돌다가 map[x][y] == '1'이면 출구를 만났으므로 최솟값을 저장하고 종료 ~~!!
q.isEmpty()가 true가 되도록 진행한 후 최솟값이 초기값과 같다면 답이 없는 것이기 때문에 -1를 리턴한다

소스코드

// 패키지 생략
public class Main {
	private static int M;
	private static int N;
	private static char[][] map;
	static boolean[][][] visit;
	static int dx[] = { 1, -1, 0, 0 };
	static int dy[] = { 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());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		// state, N, M
		visit = new boolean[1 << 6][N][M];
		map = new char[N][M];
		Queue<Loc> q = new LinkedList<>();
		for (int i = 0; i < N; i++) {
			String t = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = t.charAt(j);
				if (map[i][j] == '0') {
					q.add(new Loc(i, j, 0, 0)); // 초기 위치 큐에 삽입
					visit[0][i][j] = true;
					map[i][j] = '.';
				}
			}
		}
		//
		int min = Integer.MAX_VALUE;

		while (!q.isEmpty()) {
			Loc curr = q.poll();
			if (map[curr.x][curr.y] == '1') { // 출구 도착하면 끝
				min = curr.steps;
				break;
			}
			for (int i = 0; i < 4; i++) {
				int nx = curr.x + dx[i];
				int ny = curr.y + dy[i];
				if (nx > -1 && ny > -1 && nx < N && ny < M && map[nx][ny] != '#' && !visit[curr.state][nx][ny]) {
					int v = map[nx][ny];
					if (v - 65 >= 0 && v - 65 <= 5 && (curr.state & (1 << v - 65)) == 0) { // 문이면서 열쇠가 없는 경우
						continue;
					}
					visit[curr.state][nx][ny] = true; // 현재 상태에 방문처리

					if (v - 97 >= 0 && v - 97 <= 5) { // 열쇠인경우, 열쇠 상태비트를 더해서 큐에 추가
						q.add(new Loc(nx, ny, (curr.state | 1 << map[nx][ny] - 97), curr.steps + 1));
					} else { // 그 외
						q.add(new Loc(nx, ny, curr.state, curr.steps + 1));
					}
				}
			}
		}
		System.out.println(min == Integer.MAX_VALUE ? -1 : min);
	}
}

class Loc {
	int x;
	int y;
	int state;
	int steps;

	public Loc(int x, int y, int state, int steps) {
		super();
		this.x = x;
		this.y = y;
		this.state = state;
		this.steps = steps;
	}
}