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

https://www.acmicpc.net/problem/1194

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

해결 방안

1. 2차원 map배열과 3차원 visited배열을 만든다.

1-1. visited[N][M][64] : 키는 A~F까지 존재 -> 2^6 = 64

2. map을 입력받으며 민식이의 현재 위치를 기억한다.

3. bfs를 진행한다.

4. 출구를 만나면 종료 후 답을 출력한다.

 

추가

비트마스킹을 사용하는 법에 익숙해지자. 복잡할 것 같지만 훨씬 간단하게 작성 가능.

 

전체 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static class Point {
		int x, y, cnt, bit;

		Point(int x, int y, int cnt, int bit) {
			this.x = x;
			this.y = y;
			this.cnt = cnt;
			this.bit = bit;
		}
	}

	static int N, M;
	static char[][] map;
	static boolean[][][] visited;
	static int[] dr = { -1, 0, 1, 0 };
	static int[] dc = { 0, 1, 0, -1 };
	static int ans;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); // 세로
		M = sc.nextInt(); // 가로
		map = new char[N][M];

		Queue<Point> queue = new LinkedList<>();
		visited = new boolean[N][M][64];

		for (int i = 0; i < N; i++) {
			String s = sc.next();
			for (int j = 0; j < M; j++) {
				map[i][j] = s.charAt(j);
				if (map[i][j] == '0') { // 현재 위치
					queue.add(new Point(i, j, 0, 0));
					visited[i][j][0] = true;
				}
			}
		}
		ans = -1;

		while (!queue.isEmpty()) {
			Point p = queue.poll();
			int i = p.x;
			int j = p.y;
			int cnt = p.cnt;
			int bit = p.bit;

			if (map[i][j] == '1') { // 출구
				ans = cnt;
				break;
			}

			if (map[i][j] == '#') // 벽
				continue;

			if (map[i][j] >= 'A' && map[i][j] <= 'F') { // 대문자 : 문
				int n = map[i][j] - 65;
				if ((bit & (1 << n)) == 0)
					continue;

			}

			if (map[i][j] >= 'a' && map[i][j] <= 'f') { // 소문자 : 열쇠
				int n = map[i][j] - 97;
				if ((bit & (1 << n)) != 1)
					bit |= (1 << n);
			}

			for (int d = 0; d < 4; d++) {
				int nr = i + dr[d];
				int nc = j + dc[d];

				if (isIn(nr, nc) && !visited[nr][nc][bit]) {
					queue.add(new Point(nr, nc, cnt + 1, bit));
					visited[nr][nc][bit] = true;
				}
			}
		}

		System.out.println(ans);
	}

	private static boolean isIn(int nr, int nc) {
		if (nr < 0 || nc < 0 || nr >= N || nc >= M)
			return false;
		else
			return true;
	}
}