[백준] JAVA - 1194. 달이 차오른다,가자.

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

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

생각

BFS + 3차원 상태 배열 + 비트마스킹을 모두 생각해야하는 문제였습니다 ㅜㅜ

 

( 비트마스킹을 통해 상태를 표현하는게 더 쉬운 문제 : 백준 15683 감시 hyewon-study-log.tistory.com/106?category=976036 )

[백준] JAVA - 15683. 감시

 

현재 위치에서 내가 어떤 열쇠 조합을 가지고 있느냐에 따라서 이동을 할수있는지 없는지가 나뉘게됩니다. 따라서 현재 위치에서 내가 가지고 있는 열쇠의 상태를 저장하기 위해 3차원 배열이 필요합니다.

 

• dist[y][x][k] : (y,x) 에서 내가 가지고 있는 열쇠의 조합을 비트로 표현.
• 열쇠를 a(1<<0), b(1<<1), c(1<<2), d(1<<3), e(1<<4), f(1<<5)인 비트로 나타낼수있으므로 모든열쇠를 가졌다면 111111(63)이므로 인덱스 사이즈를 64로 설정했습니다.
• 열쇠칸이라면 or 연산을 통해 해당 열쇠의 비트를 1로 바꿔줍니다.
• 문이라면 and 연산을 통해 해당 열쇠가 있는지 확인합니다. 해당 열쇠가 없다면 이동이 불가능합니다.
• 출구는 여러 개일 수있으므로, 좌표값이 1이라면 바로 리턴합니다.

Java Code

package com.java.algorithm;

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

public class BOJ_1194_달이차오른다가자 {
	static int R,C;
	static char[][] map;
	static int[][][] dist; //dist[y][x][k] : y좌표, x좌표, 가지고있는열쇠상태 -> 가지고있는열쇠상태에 따라  111111 -> 63
	static int[] dy = {1,-1,0,0};
	static int[] dx = {0,0,1,-1};
	static class Pos{
		int y;
		int x;
		int k;
		public Pos(int y, int x, int k) {
			super();
			this.y = y;
			this.x = x;
			this.k = k;
		}
		@Override
		public String toString() {
			return "Pos [y=" + y + ", x=" + x + ", k=" + k + "]";
		}
		
	}
	static Queue<Pos> q;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		map = new char[R][C];
		dist = new int[R][C][64];
		
		q = new LinkedList<Pos>();
		
		for (int i = 0; i < R; i++) {
			char[] temp = br.readLine().toCharArray();
			for (int j = 0; j < C; j++) {
				map[i][j] = temp[j];
				if(map[i][j] == '0') {
					q.add(new Pos(i,j,0));
				}
			}
		}
		
		System.out.println(byBFS());
		
	} // end of main
	
	
	private static int byBFS() {
		
		while(!q.isEmpty()) {
			Pos now = q.poll();
			if(map[now.y][now.x] == '1') {
				return dist[now.y][now.x][now.k];
			}
			for (int d = 0; d < 4; d++) {
				int ny = now.y + dy[d];
				int nx = now.x + dx[d];
				int nk = now.k;
				if(ny >= R || ny < 0 || nx >= C || nx < 0) continue;
				
				char next = map[ny][nx];
				
				if('a' <= next && next <= 'f') { // 열쇠일때
					nk |= (1 << (next-'a')); //or 연산으로 열쇠 얻기
				}else if('A' <= next && next <= 'F') { // 문일때
					//열쇠없으면 못감
					if((nk & (1<<(next-'A'))) == 0) continue;
				}
				if(dist[ny][nx][nk] > 0 || next == '#') continue;
				
				q.add(new Pos(ny,nx,nk));
				dist[ny][nx][nk] = dist[now.y][now.x][now.k] + 1;
				
			}
		}
		return -1;
	}

}