달이 차오른다, 가자. [백준 1194][골드1][Java]

 

[광고 누르면 오늘의 행운 상승!!]

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

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

문과 감성 충만한 시뮬레이션 bfs 문제.

3차원 배열을 비트마스킹을 사용하여 모든 키를 주웠을 경우의 수 만큼 만들었다.

package WorkShop;

import java.io.*;
import java.util.*;

class MPos{
	int row, col, World;
	
	int[] keyList;
	int dis;
	int cnt;
	
	public MPos(int row, int col, int[] keyList, int dis, int World) {
		this.row = row;
		this.col = col;
		this.keyList = keyList;
		this.dis = dis;
		this.World = World;
	}
}
public class 달이차오른다가자 {
	
	//민식이를 도와주자.
	public static int min = Integer.MAX_VALUE;
	public static char map[][];
	public static boolean visit[][][];
	public static final int[] dx = {-1,0,1,0};
	public static final int[] dy = {0,1,0,-1};
	public static int R, C;
	public static Queue<MPos> q;
	public static int cnt;
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("test.txt"));
		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];
		visit = new boolean[64][R][C];
		q = new LinkedList<>();
		
		for (int i = 0; i < R; i++) {
			char ch[] = br.readLine().toCharArray();
			for (int j = 0; j < C; j++) {
				map[i][j] = ch[j];
				
				if(map[i][j] == 48) {
					q.add(new MPos(i,j, new int[6] ,0,0)); 
					visit[0][i][j] = true;
					//민식이의 현재 위치와 주머니를 하나 만들어줌 + 지나온 거리와 월드
				}
			}
		}
		
		bfs();
		if(min != Integer.MAX_VALUE) {
			System.out.println(min);
			return;
		}
		System.out.println(-1);
	}
	public static void bfs() {
		while(!q.isEmpty()) {
			
			MPos pos = q.poll();

			if(map[pos.row][pos.col] == 49) {
				min = Math.min(pos.dis, min);
			}
			
			if(map[pos.row][pos.col] >= 'a' && map[pos.row][pos.col] <= 'f') {
				//키를 주우면 키를 숫자로 변환하여 월드에 삽입.
				pos.keyList[map[pos.row][pos.col]-'a'] = 1;
				pos.World = FindWorld(pos);
				visit[pos.World][pos.row][pos.col] = true; //방문처리
			}
			
			for (int i = 0; i < 4; i++) {
				int nx = pos.row + dx[i];
				int ny = pos.col + dy[i];
				int nw = pos.World;
				
				if(Check(nx, ny))  continue;
				if(map[nx][ny] == '#' || visit[nw][nx][ny]) continue;
				
				if (map[nx][ny] >= 'A' && map[nx][ny] <= 'F') {
					int size = pos.keyList.length;
					if (pos.keyList[map[nx][ny] - 'A'] == 1) {
						// 맞는 키라면
						int[] list = pos.keyList.clone();
						q.add(new MPos(nx, ny, list, pos.dis + 1, nw));
						visit[nw][nx][ny] = true; //방문처리
					}
				} else {
					int[] list = pos.keyList.clone();
					q.add(new MPos(nx, ny, list, pos.dis + 1, nw));
					visit[nw][nx][ny] = true; //방문처리
				}
			}
		}
	}
	private static int FindWorld(MPos pos) {
		//차원을 계산.

		int temp = 0;
		for (int j = 0; j < pos.keyList.length; j++) {
			if(pos.keyList[j] ==1 ) {
				temp += (1<<j);
			}
		}
		return temp; //숫자로 변환된 2진수
	}
	private static boolean Check(int nx, int ny) {
		return nx < 0 || nx >= R || ny < 0 || ny >= C;
	}

}