백준_1194 달이 차오른다, 가자.(자바) / BFS + 비트마스킹

시간 & 메모리 제한

문제

입력 & 출력

BFS & 비트 마스킹을 통한 문제풀이

package com.Back;

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 Back_1194 {
	static int N, M;
	static char[][] map;
	static point me;
	static boolean [][][] visited; // x,y 위치에 k 의 상태로 방문 여부
	static int[] dx= {-1,1,0,0};
	static int[] dy= {0,0,-1,1};
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		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 temp = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j]=temp.charAt(j);
				
				if(map[i][j]=='0') me = new point(i,j,0,0);
			}
		}
		bfs();
		
	}
	private static void bfs() {
		Queue<point> q = new LinkedList<>();
		q.add(new point(me.x,me.y,me.k,me.cnt));
		visited[me.x][me.y][0] =true;
		while(!q.isEmpty()) {
			point temp = q.poll();
			int x = temp.x;
			int y = temp.y;
			int cnt = temp.cnt;
			int key = temp.k;
			
			//1에 도착을 한경우-> 종료조건
			if (map[x][y] == '1') {
				System.out.println(cnt);
				return;
			}
			
			for (int k = 0; k < 4; k++) {
				int xx = x + dx[k];
				int yy = y + dy[k];
				if(xx<0 || yy<0 || xx>=N || yy>=M ) continue;
				if(map[xx][yy]=='#' || visited[xx][yy][key]) continue;
				if(map[xx][yy]>='a' && map[xx][yy]<='f') {
					int tkey = (1<<(map[xx][yy]-'a')) | key;
					
					if(!visited[xx][yy][tkey]) {
						visited[xx][yy][tkey] = true;
						visited[xx][yy][key] = true;
						q.add(new point(xx, yy, tkey, cnt+1));
					}
				}else if(map[xx][yy] >= 'A' && map[xx][yy] <= 'F' ) {
					int door = (1<<(map[xx][yy])-'A') & key;
					
					if(door>0) {
						visited[xx][yy][key] = true;
						q.add(new point(xx, yy, key, cnt+1));
					}
				}else {
					visited[xx][yy][key] = true;
					q.add(new point(xx, yy, key, cnt+1));
				}
			}
		}
		System.out.println(-1);
	}
	static class point{
		int x;
		int y;
		int k;
		int cnt;
		public point(int x, int y, int k,int cnt) {
			this.x = x;
			this.y = y;
			this.k = k;
			this.cnt=cnt;
		}
		
	}
}

- 이 문제의 경우는 BFS 와 비트 마스킹을 이용해서 풀었습니다.

 

- 이 문제를 푸는 아이디어는 일단 키가 있는 위치로 이동합니다. 물론 1에 도착하거나 이동할 수 없는 경우

 

미리 while문을 탈출하게 됩니다.

 

그리고, 키를 찾게 되면 다시 돌아다니면서 키를 통해서 추가적인 통로로 이동을 하게 됩니다. 결국엔 1이라

 

는 위치를 찾게 됩니다.

 

- Step1. visited map을 초기화 하고 값을 받아옵니다. 여기서 내 위치는 따로 담아둡니다. 여기서 visited 를 3차원 배열

 

로 만든 이유는 키를 획득하면 visited에 대해서 초기화가 필요하기 때문입니다.

 

또한 [N][M][64]에서 64인 이유는 6개의 키의 존재 여부를 표시할때 0 0 0 0 0 0 2진수로 볼때 최대 64이기 때문입니다.

 

키를 얻었는데, f 키만 있는경우 0 0 0 0 0 1 이므로 visited[x][y][32]의 값에 대해서 이동을 다시 진행하겠죠?

 

- Step2. BFS를 진행합니다. tkey에서는 여러개의 키를 가지고 있게 만들기 위해서 |로 표현을 했습니다.

 

- Step3. door의 경우는 그 위치에서의 내 키가 있는지를 확인해야 하므로 둘다 참일 경우를 확읺해야 하기 때문에 &로

 

확인을 했습니다.

 

- 비트마스킹을 알면 좀 수월하게 풀리는 문제였던거 같습니다.... 알고리즘에 관한 지식은 끝이 없는거 같네요