[BOJ-1194]달이차오른다, 가자 -Java

www.acmicpc.net/problem/1194

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

package 시뮬레이션;

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

public class boj_1194_달이차오른다_가자 {
	static int N, M, result;
	static char map[][];
	static boolean visited[][][];
	static int dx[]={-1,1,0,0};
	static int dy[]={0,0,1,-1};
	static class Info{
		int x,y,index,cnt;
		public Info(int x, int y, int index, int cnt) {
			this.x = x;
			this.y = y;
			this.index = index;
			this.cnt = cnt;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int sx=0,sy=0;
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		map = new char[N][M];
		visited = new boolean[N][M][64];

		for (int i = 0; i < N; i++) {
			String input = br.readLine();
			map[i] = input.toCharArray();
		}

		loop: for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == '0') {
					sx=i;
					sy=j;
					break loop;
				}
			}
		}
		
		solve(sx,sy);
		
		result =result==0? -1 : result;
		System.out.println(result);

	}

	private static void solve(int sx, int sy) {
		Queue <Info> queue = new LinkedList<>();
		queue.add(new Info(sx,sy,0,0));
		visited[sx][sy][0]=true;
		
		while(true) {
			int size=queue.size();
			if(size==0) return; //끝
			
			for(int i=0; i<size; i++) {
				Info info=queue.poll();
				
				if(map[info.x][info.y]=='1') { //출구 만나면 
					result = info.cnt;
					return;
				}
				
				for(int d=0; d<4; d++) {
					int nx=info.x+dx[d];
					int ny=info.y+dy[d];
					
					if(nx<0 || ny<0 || nx>=N || ny>=M || map[nx][ny]=='#' || visited[nx][ny][info.index])
						continue; //범위 넘어가거나, 벽이거나, 방문 했거나 하면 스킵
					else if(map[nx][ny]>='a' && map[nx][ny]<='f') { //열쇠 가졌다면
						int newIndex=info.index | (1<<map[nx][ny]-'a'); //새로운 인덱스 구해주고
						queue.offer(new Info(nx,ny,newIndex,info.cnt+1));
						visited[nx][ny][newIndex]=true;
					}
					else if(map[nx][ny]>='A'&& map[nx][ny]<='F') { //문 만났을 때
						if((info.index & (1<<map[nx][ny]-'A'))==0) continue; //열쇠없으면 스킵 
						queue.offer(new Info(nx,ny,info.index, info.cnt+1)); //있으면 큐에 push
						visited[nx][ny][info.index]=true;
					}
					else { //빈 곳
						queue.offer(new Info(nx,ny,info.index, info.cnt+1)); //있으면 큐에 push
						visited[nx][ny][info.index]=true;
					}
					
				}
			}
			
		}
	}

}

소요시간 : 1시간 5분

 

비트마스킹 + BFS문제입니다.

예전에 싸피에서 푼 문제인데 오랜만에 다시 풀어봤습니다.

 

비트마스킹을 사용한 이유는 열쇠를 가지고 있는지 아닌지 확인하기 위해서입니다.

우선 비트마스킹에 대해 설명하자면

 

shift

1<<2  이 식은 1을 왼쪽으로 두번 옮기겠다는 뜻입니다.

1 -> 100  즉 1에서 x2x2 한 4가 됩니다. ( 001 -> 100 )

or

2 | 4 = 10 or 100 -> 110 이 됩니다.   (각 비트중 한개라도 1이면 1이 나옵니다)

and

2 & 4= 10 and 100 -> 000 이 됩니다. (두개의 비트 모두가 1이면 1이 나옵니다.)

 

a = 000001

b = 000010

c = 000100 

처럼 비트마스킹해서 사용합니다.

 

 

1. 소문자를 만났을 때 (or 이용)

만약 a를 만났다고 하면 000001 처럼 비트마스킹을 해줍니다.

그리고 c까지 만났다면 000101 처럼 비트마스킹을 해줍니다.

 

2. 대문자를 만났을 때 (and이용)

만약 대문자 A를 만났다면 현재 비트는 000101 입니다.

여기서 소문자 a를 가지고 있는지 확인하기 위해 

000101 & 1 을 진행합니다. 이 때 0이 아니라면 a를 가지고 있는 것입니다. 

 

만약 대문자 D를 만났다면 

000101& 001000 를 통해 확인합니다 -> 결과가 0이니 소문자 d를 가지고 있지 않다는 뜻입니다.

 

이런식으로 푸시면 됩니다...

 

끝~