백준 1194번: 달이 차오른다, 가자. [BFS][비트마스킹][그래프] - Java

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

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

 

 

<Java코드>

 

열쇠 유무를 비트마스킹을 이용해 관리한다.

 

* 추가 테스트 케이스

4 5
#f#..
#.#..
#a#..
0.FA1

답: 10

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		char map[][] = new char[N][M];
		int visit[][][] = new int[N][M][1 << 6]; // 6개의 열쇠 보유 여부 비트마스킹

		Queue<Pos> q = new LinkedList<Pos>();

		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = str.charAt(j);

				if (map[i][j] == '0') { // 민식이 위치
					q.add(new Pos(i, j, 0));
					visit[i][j][0] = 0;
				}
			}
		}

		int dx[] = { 0, 1, 0, -1 };
		int dy[] = { 1, 0, -1, 0 };

		int ans = Integer.MAX_VALUE;

		while (!q.isEmpty()) {
			Pos now = q.poll();
//			System.out.println("x: "+now.x+", y: "+now.y+", now.key:"+now.key+"==> visit: "+visit[now.x][now.y][now.key]);
			if (map[now.x][now.y] == '1') {
				ans = Math.min(visit[now.x][now.y][now.key], ans);
				// System.out.println(visit[now.x][now.y][now.key]);
				break;
			}

			// 이동
			for (int i = 0; i < 4; i++) {
				int nx = now.x + dx[i];
				int ny = now.y + dy[i];

				if (nx < 0 || nx >= N || ny < 0 || ny >= M)
					continue;

				if (map[nx][ny] == '#')
					continue;

				if (visit[nx][ny][now.key] == 0) {

					// 열쇠인가?
					if (map[nx][ny] >= 'a' && map[nx][ny] <= 'f') {
						int newMask = 1 << map[nx][ny] - 'a'; // a=1, b=2, c=3...
						
						if (visit[nx][ny][now.key | newMask] == 0) {
							visit[nx][ny][now.key | newMask] = visit[now.x][now.y][now.key] + 1;
							q.add(new Pos(nx, ny, now.key | newMask));
						}
					}
					// 문인가?
					else if (map[nx][ny] >= 'A' && map[nx][ny] <= 'F') {

						// 해당 하는 문의 열쇠를 가지고 있는가?
						int door = 1 << map[nx][ny] - 'A';
						if ((now.key & door) == door) {
							visit[nx][ny][now.key] = visit[now.x][now.y][now.key] + 1;
							q.add(new Pos(nx, ny, now.key));
						}

					} else {
						visit[nx][ny][now.key] = visit[now.x][now.y][now.key] + 1;
						q.add(new Pos(nx, ny, now.key));
					}
				}

			}
		}

		if (ans == Integer.MAX_VALUE)
			System.out.println(-1);
		else
			System.out.println(ans);

	}

	static class Pos {
		int x;
		int y;
		int key;

		public Pos(int x, int y, int key) {
			this.x = x;
			this.y = y;
			this.key = key;
		}
	}
}