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

문제

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

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

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

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

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

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

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

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

입력

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

출력

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

예제 입력 1 

1 7
f0.F..1

예제 출력 1 

7

예제 입력 2 

5 5
....1
#1###
.1.#0
....A
.1.#.

예제 출력 2 

-1

예제 입력 3 

7 8
a#c#eF.1
.#.#.#..
.#B#D###
0....F.1
C#E#A###
.#.#.#..
d#f#bF.1

예제 출력 3 

55

예제 입력 4 

3 4
1..0
###.
1...

예제 출력 4 

3

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

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

---

문제 풀이

 해당 문제는 최단 거리 문제이다. 하지만 문이 존재하고, 해당 문에 맞는 열쇠를 가지고 있어야지만 해당 문을 통과할 수 있다는 조건이 존재한다.

 이 조건을 visited에 추가하여 문제를 풀 수 있지만, 문이 많이 존재하게 된다면 매우 큰 배열이 필요할 것이다. 그렇기에 키에 대한 정보를 비트단위로 저장하면 해당 문제를 알맞게 풀 수 있다.

 

기존 최단 거리를 구하는 방식을 동일하기에 해당 부분은 제외하고 설명하겠다.(BFS 알고리즘)

 

우선 visited를 2중 배열이 아닌 3중 배열로 생성하여 key값을 저장할 수 있도록 한다.

boolean[][][] visited = new boolean[col][row][1<<doors.size()]; 
// 이때 비트 마스킹을 위해 '1<<문의 개수' 크기로 선언해준다

 

이 후 qu에 있는 데이터를 처리하면서 이동 경로에 A~Z(문)이 존재할 경우 가지고 있는 key에서 해당 문의 index 부분이 1이면 통과하고, 0이라면 continue로 문을 통과하지 않게 설계한다.

...
int mx = x + dx[i];
int my = y + dy[i];
if(mx < 0 || mx >= row || my < 0 || my >= col || board[my][mx].equals("#") 
        || visited[my][mx][key]) continue;

if( board[my][mx].codePointAt(0) >= "A".codePointAt(0) 
   && board[my][mx].codePointAt(0) <= "Z".codePointAt(0) 
   && (key & (1 << doors.indexOf(board[my][mx]))) != (1 << doors.indexOf(board[my][mx]))) {
    continue;
}
...

 

이동 경로에 a~z(key)가 존재한다면, 해당 키를 기존에 가지고 있다면 일반적인 움직임으로 작동하고, 만약 기존에 가지고 있지 않는 키라면 key의 비트에서 해당 키의 index를 1로 변경하고, 해당 키를 전달해준다.

...
if(board[my][mx].codePointAt(0) >= "a".codePointAt(0) 
        && board[my][mx].codePointAt(0) <= "z".codePointAt(0)) {
    char target = (char) (board[my][mx].codePointAt(0) - 32);
    String str = Character.toString(target);
    if(doors.contains(str)) {
        int tempKey = key | (1<<doors.indexOf(str));
        qu.add(new Pos(mx,my,tempKey));
        count.add(c+1);
    }else {
        qu.add(new Pos(mx,my,key));
        count.add(c+1);
    }
}else {
    qu.add(new Pos(mx,my,key));
    count.add(c+1);
}
...

---

풀이 코드

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.io.*;

public class Main {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static StringTokenizer st;
	
	public static int[] dx = {0,1,0,-1};
	public static int[] dy = {-1,0,1,0};
	public static String[][] board;
	public static ArrayList<Pos> destinations = new ArrayList<>(); 
	public static ArrayList<String> doors = new ArrayList<>();
	public static ArrayList<String> keys = new ArrayList<>(); 
	public static class Pos{
		int x;
		int y;
		int key;
		
		public Pos() {}
		public Pos(int x, int y) {
			this.x = x;
			this.y = y;
			this.key = 0;
		}
		public Pos(int x, int y, int key) {
			this.x = x;
			this.y = y;
			this.key = key;
		}
		@Override
		public String toString() {
			return "pos => x : " + x + ", y = " + y + " key = " + Integer.toBinaryString(key);
		}
	}
	
	public static void main(String[] args) throws IOException{
		st = new StringTokenizer(br.readLine());
		
		int col = Integer.parseInt(st.nextToken());
		int row = Integer.parseInt(st.nextToken());
		
		board = new String[col][row];
		Pos curPos = new Pos();
		
		for(int c = 0; c < col;c++) {
			board[c] = br.readLine().split("");
			
			for(int r = 0; r < row; r++) {
				if(board[c][r].equals("0")) {
					curPos.x = r;
					curPos.y = c;
				}else if(board[c][r].equals("1")) {
					destinations.add(new Pos(r,c));
				}else if(board[c][r].codePointAt(0) >= "A".codePointAt(0) && board[c][r].codePointAt(0) <= "Z".codePointAt(0)) {
					if(!doors.contains(board[c][r]))
						doors.add(board[c][r]);
				}else if(board[c][r].codePointAt(0) >= "a".codePointAt(0) && board[c][r].codePointAt(0) <= "z".codePointAt(0)) {
					if(!keys.contains(board[c][r]))
						keys.add(board[c][r]);
				}
			}
		}
		
		doors.sort(null);

		boolean[][][] visited = new boolean[col][row][1<<doors.size()];
		Queue<Pos> qu = new LinkedList<>();
		Queue<Integer> count = new LinkedList<>();
		
		qu.add(curPos);
		count.add(0);
		
		boolean possible = false;
		while(!qu.isEmpty()) {
			Pos cur = qu.poll();
			int x = cur.x;
			int y = cur.y;
			int key = cur.key;
			int c = count.poll();
			
			
			if(board[y][x].equals("1")) {
				System.out.println(c);
				possible = true;
				break;
			}
			
			if(visited[y][x][key])continue;
			visited[y][x][key] = true;
			
			for(int i = 0 ; i < 4; i++) {
				int mx = x + dx[i];
				int my = y + dy[i];
				if(mx < 0 || mx >= row || my < 0 || my >= col || board[my][mx].equals("#") 
						|| visited[my][mx][key]) continue;
			
				if( board[my][mx].codePointAt(0) >= "A".codePointAt(0) && board[my][mx].codePointAt(0) <= "Z".codePointAt(0) && (key & (1 << doors.indexOf(board[my][mx]))) != (1 << doors.indexOf(board[my][mx]))) {
					continue;
				}
				
				if(board[my][mx].codePointAt(0) >= "a".codePointAt(0) 
						&& board[my][mx].codePointAt(0) <= "z".codePointAt(0)) {
					char target = (char) (board[my][mx].codePointAt(0) - 32);
					String str = Character.toString(target);
					if(doors.contains(str)) {
						int tempKey = key | (1<<doors.indexOf(str));
						qu.add(new Pos(mx,my,tempKey));
						count.add(c+1);
					}else {
						qu.add(new Pos(mx,my,key));
						count.add(c+1);
					}
				}else {
					qu.add(new Pos(mx,my,key));
					count.add(c+1);
				}
			}
		}
		if(!possible)System.out.println(-1);
		
	}
}