백준_달이 차오른다, 가자._1194[Java]

문제

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

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

 

앞서 풀었던 욕심쟁이 판다 문제와 흐름은 방법이 비슷한 부분이 있는데

이 문제의 핵심인 열쇠를 가지고 있는지 확인하는 과정에서 비트마스킹 방식이 들어가니 어려웠다. 

비트마스킹을 배우게 된 문제 ! 꺅 

 

 

흐름

BFS를 이용한 메소드를 호출한다.

완전 탐색을 강행하는데 한번 다녀온 위치는 이미 다녀왔음을 기록해둬 중복 방문 횟수를 줄인다. 

출구(1)를 찾았을 경우에는 메소드를 종료한다. 

 

3차원 배열인 visit 에 위치값 X, Y 그리고 해당 위치에 갔을 때 가지게 되는 키 정보를 담는다. 

키 정보는 아래와 같이 2진수로 담는다.

키를 획득했을 경우에는 1,  없을 경우에는 0으로 지정한다. 키 별 위치는 다음과 같다. 

    a    b    c    d    e    f                          

예를 들어 a키와 d키, 두 가지 키를 소유하고 있을 경우에는 100100(2)

 

따라서 f라는 키를 발견했을 때 1 << 'f' - 'a' 는 1 << 5 이므로 2의 6승 = 100000(2)다.

이 값을 OR연산하면 새로 획득한 키 정보를 추가할 수 있다. 

* 여기서 'a' , 'b', 'c', 'd', 'e', 'f', 는 각각 아스키코드로 97, 98, .. 102라는 것을 알아두자. 

 

문을 발견했을 때는 비슷한 방법으로 키를 가지고 있는지 확인하고 가지고 있다면 이동하고 

가지고 있다면 이동하지 않는다. 

 

코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int N, M;
	static char[][] miro;
	static boolean[][][] visit;
	static int result = 0;

	static class Dot{
		int x;
		int y;
		int key;
		
		Dot(int x, int y, int key){
			this.x = x;
			this.y = y;
			this.key = key;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		sc.nextLine();
		
		Dot start = null;
		miro = new char[N][M];
		String[] s = new String[N];
		visit = new boolean[N][M][1 << 6]; // 2의 6승을 만들어준다. 
		
		for(int i = 0; i < N; i++) {
			s = sc.nextLine().split("");
			for(int j = 0; j < M; j++) {
				miro[i][j] = s[j].charAt(0);
				if(miro[i][j] == '0') { // 민식이 위치
					start = new Dot(i, j, 0);
				}
			}
			
		}
		
		result = solution(start);
		System.out.println(result);
		sc.close();
	}

	// 하 상 우 좌 
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, 1, -1};
	
	private static int solution(Dot start) {
		Queue<Dot> q = new LinkedList<Dot>();
		q.add(start);
		// peek : 가장 앞쪽에 위치한 값을 리턴해준다. 삭제X (가장 먼저 나갈 아이)
		visit[q.peek().x][q.peek().y][0] = true;

		int time = 0;
		while(!q.isEmpty()) {
			int size = q.size();
			for(int qsize = 0; qsize < size; qsize++) {
				// poll : 가장 앞쪽 위치한 값 리턴 및 q에서 삭제 
				Dot t = q.poll()	; 
				int curX = t.x;
				int curY = t.y;
				int curKey = t.key;
				
				if(miro[curX][curY] == '1') {
					return time;
				} // 기저사례 
				
				// 이동 : 상하좌우 가능 
				for(int i = 0; i < 4; i++) {
					int nextX = curX + dx[i];
					int nextY = curY + dy[i];
					int key = curKey;
					
					// 장외 
					if(nextX >= N || nextY >= M || nextX < 0 || nextY < 0) {
						continue;
					}
                    
					// 벽 발견 
					if(miro[nextX][nextY] == '#') {
						continue;
					}
                    
					// 키 발견 
					if('a' <= miro[nextX][nextY] && miro[nextX][nextY] <= 'f') {
						key |= (1 << miro[nextX][nextY] - 'a');
					}
					
					// 문 발견 
					if('A' <= miro[nextX][nextY] && miro[nextX][nextY] <= 'F') {
						if((key & (1 << (miro[nextX][nextY] - 'A'))) == 0) { // 키를 가지고 있지 않다면 
							continue;
						}
					}
					
					// 방문 이전에 했다면 패스 
					if(visit[nextX][nextY][key]) {
						continue;
					}
					
					visit[nextX][nextY][key] = true;
					q.add(new Dot(nextX,nextY, key)); 
					
				}
			}
			time++;
		}
		return -1;
		
	}

}

 

참고

- 비트 연산 참고하기

https://heedipro.tistory.com/245

불러오는 중입니다...

 

- 코드 및 흐름 참고

https://zoonvivor.tistory.com/158

[BOJ] 백준 1194 - 달이 차오른다, 가자. (자바)

 

- 알고리즘 문제 풀 때 C++로 푼 거 보는것도 재미땨  

https://jason9319.tistory.com/214

BOJ)1194 달이 차오른다, 가자.