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

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

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

문제

지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다.

민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다.

하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다.

영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다.

민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고, 여행길을 떠나기 위해 미로를 탈출하려고 한다. 미로는 다음과 같이 구성되어져있다.

• 빈 곳 : 언제나 이동할 수 있다. ('.‘로 표시됨)
• 벽 : 절대 이동할 수 없다. (‘#’)
• 열쇠 : 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 집는다. (a - f)
• 문 : 대응하는 열쇠가 있을 때만 이동할 수 있다. (A - F)
• 민식이의 현재 위치 : 빈 곳이고, 민식이가 현재 서 있는 곳이다. (숫자 0)
• 출구 : 달이 차오르기 때문에, 민식이가 가야하는 곳이다. 이 곳에 오면 미로를 탈출한다. (숫자 1)

달이 차오르는 기회를 놓치지 않기 위해서, 미로를 탈출하려고 한다. 한 번의 움직임은 현재 위치에서 수평이나 수직으로 한 칸 이동하는 것이다.

민식이가 미로를 탈출하는데 걸리는 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다. 0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다.

출력

첫째 줄에 민식이가 미로를 탈출하는데 드는 이동 횟수의 최솟값을 출력한다. 만약 민식이가 미로를 탈출 할 수 없으면, -1을 출력한다.

 

풀이방법

- 문제의 도입이 무슨 말을 하는지 한참 읽었으나, 의미 없는 말 같다.

- 문제는 이동 횟수의 최솟값을 구하기 위해 BFS를 사용했다.

- 추가적으로, 키를 얻었을 때의 배열을 어떻게 관리해야 할지 상당히 고민했다.

- 그 결과, 각 키를 얻었을 때, 얻지 못했을 때= 총 64( = 2^6 ) 가지의 visit 배열인 3차원 배열로 관리방법을 찾았다.

 

- 또한, 시간초과를 방지하기 위해 반드시 비트마스킹을 통해 moon 클래스를 관리 해야 한다고 하는데 

  아직 어떻게 하면 시간 초과가 나는지 잘 모르겠다.

  이 부분에 대해 잘 아시는 분은 알려주시면 감사하겠습니다.

 

- 따라서 비트마스킹을 통해 각 객체들이 어떤 키를 가지고 있는지 저장해두었다.

 

결론, BFS + visit[][][ 1<<6] + 비트마스킹 사용 

 

EX.

 

• 키의 상태는 2진법으로 나타낼 수 있으며 각 비트는 특정 열쇠를 나타낸다.
  • 오른쪽에서 왼쪽으로 a ~ f의 열쇠를 나타낸다.
  • 000001(2) 열쇠 a를 가지고 있음
  • 100000(2) 열쇠 f를 가지고 있음
• 열쇠에 도달했을 때 해당 키를 추가하려면 | 연산을 사용한다.
  • a열쇠에 도달했을 때 &연산으로 먼저 이미 가지고 있는지 확인한다.
  • 없다면 000001(2)와 현재 열쇠 상태를 | 연산하여 합쳐준다.
• 문에 도달했을 때 해당 키를 가지고 있는지 확인하기 위해서는 & 연산을 사용한다.
  • A문에 도달했을 때 필요한 열쇠는 a이므로 000001(2)와 현재 열쇠 상태를 &연산 했을 때 가지고 있다면 000001(2)를 리턴한다.

코드

package 알고리즘스터디문제;

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

public class 달이차오른다가자_1194 {

	static int[] dr = { -1, 0, 1, 0 };
	static int[] dc = { 0, 1, 0, -1 };

	static int N, M; // N : row , M : column
	static boolean[][][] visited; // 방문 처리 할거
	static char[][] map; // 맵 생성
	static Queue<moon> queue;
	static int answer = -1;

	static class moon {
		int r;
		int c;
		int flag;
		int count;

		public moon(int r, int c, int flag, int count) {
			this.r = r;
			this.c = c;
			this.flag = flag;
			this.count = count;
		}

	}

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		queue = new LinkedList<>();
		N = sc.nextInt();
		M = sc.nextInt();

		map = new char[N][M];
		// visit 을 어떻게 처리해야할까? ==> 각각 키를 가지고 있는 경우의 수를 배열로 처리하자.
		visited = new boolean[N][M][1 << 6];
		int startX = 0;
		int startY = 0;
		for (int i = 0; i < N; i++) {
			String str = sc.next();
			for (int j = 0; j < M; j++) {
				map[i][j] = str.charAt(j);

				if (map[i][j] == '0') {
					startX = i;
					startY = j;
				}

			}

		}
		
		queue.add(new moon(startX, startY, 0, 0));
		bfs();

		System.out.println(answer);
	}

	static public void bfs() {

		while (!queue.isEmpty()) {
			moon Cur = queue.poll();

			if ( map[Cur.r][Cur.c] == '1' ) { // 도착지점이라면  
				answer = Cur.count;
				break;
			}
			
			for (int d = 0; d < 4; d++) {
				int nr = Cur.r + dr[d];
				int nc = Cur.c + dc[d];
				int flag = Cur.flag;
				int count = Cur.count;

				
				// boundary check, 벽도 못가게 , 해당 키 보유한 녀석이 기존에 방문했는지
				if (nr < 0 || nr >= N || nc < 0 || nc >= M || map[nr][nc] == '#' || visited[nr][nc][flag])
					continue;

				// 키를 발견했을 때,
				if (map[nr][nc] >= 'a' && map[nr][nc] <= 'f') {
					
					visited[nr][nc][flag | 1 << map[nr][nc] - 'a'] = true;
					queue.add(new moon(nr, nc, flag | 1 << map[nr][nc] - 'a', count + 1));
				}
				// 대문 발견했을 때,
				else if (map[nr][nc] >= 'A' && map[nr][nc] <= 'F') {
					
					if ( (flag & ( 1 << map[nr][nc] - 'A') ) != 0) { // 키를 가지고 있다면
						// 키 없으면 못나와 ~
						
						visited[nr][nc][flag] = true; // 방문처리하고
						queue.add(new moon(nr, nc, flag, count + 1)); // 큐에 추가
					} 
				}				
				// 그냥 통로
				else {
					
					visited[nr][nc][flag] = true;
					queue.add(new moon(nr,nc,flag,count+1));
					
				}

			}
		}
	}
	
}