[BOJ] 백준 9328번 열쇠 (Java)

#9328 열쇠

난이도 : 골드 1

유형 : 그래프 탐색 / BFS

9328번: 열쇠

▸ 문제

상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다.

상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.

• '.'는 빈 공간을 나타낸다.
• '*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
• '$'는 상근이가 훔쳐야하는 문서이다.
• 알파벳 대문자는 문을 나타낸다.
• 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.

마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.

상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.

▸ 출력

각 테스트 케이스 마다, 상근이가 훔칠 수 있는 문서의 최대 개수를 출력한다.

 

문제 풀이  

그래프 구현 문제이다. BFS와 여러 조건 분기를 통해 구현해낼 수 있다. 이러한 문제는 분기 처리를 얼마나 깔끔하게 하느냐가 중요하다. 경험상 이러한 문제를 한 번에 통과한 적은 없는 것 같다. 언제나 엣지케이스가 존재... 해당 문제에서 신경써줘야 할 엣지케이스는 입구가 되는 점에서 $, 문, 열쇠가 존재하는 경우이다. 

 

그래서 나는 입력값을 받을 때 열쇠와 키를 처리해줬고, 문은 BFS 탐색 시작하기 직전에 처리해줬다. 왜냐하면 입력에서 동시에 처리하게 되면 나중에 얻게 될 열쇠에 대해 문을 처리하지 못할 수도 있기 때문이다.

BFS 조건 분기

1) '$' 열쇠인 경우

열쇠를 획득했으므로 카운트해준다. answer++;

 

2) 'a' ~ 'z 열쇠인 경우'

key를 비트마스크를 통해 저장해준다. (26개의 키를 배열로 처리하는 것보다 비트마스킹이 더 효율적임. int형으로 거의 29개의 데이터까지는 처리가 가능하다. log(2147483647)/log(2) = 30.xxx)

 

그리고 방금 획득한 key가 만약 열쇠가 없어 들어가지 못한 Queue에 저장되어있다면 해당 watingQueue를 현재 실행중인 Queue로 옮겨준다.

// q: 현재 실행중인 큐, waitQueue : 통과하지 못한 문 저장하는 대기 큐
private static void watingQueueExtract(Queue<int[]> q, int door) {
	Queue<int[]> waitQueue = doorList.get(door);
	while(!waitQueue.isEmpty()) { // 해당 대기 큐를 현재 실행중인 큐에 옮겨준다.
		int[] wq= waitQueue.poll();
		q.add(new int[] {wq[0],wq[1]});
	}
}

 

3) 'A' ~ 'Z' 문인 경우

열쇠를 갖고 있으면 그냥 열고 지나가면 된다. 문제는 열쇠가 없는 경우이다. 2)번에서도 언급했지만 열쇠가 없는 경우에는 waitingQueue에 저장해줘야 한다. 왜냐하면 key를 얻게되면 그 부분은 탐색이 가능해지기 떄문이다.

// 통과하지 못한 문은 Map<door비트, Queue>에 저장해준다.
private static void putDoorQueue(int x, int y, int door) {
	if(doorList.containsKey(door)) {
		doorList.get(door).add(new int[] {x,y});
	}else {
		Queue<int[]> dq = new LinkedList<>();
		dq.add(new int[] {x,y});
		doorList.put(door, dq);
	}
}

 

설계

1. Map 데이터를 저장한다. map[i][j] = line.charAt(j);
   1. 입구로 해당되는 부분은 List에 저장한다.
      1. '$'인 경우, 카운트를 해준 후 '.'로 변환한다.
      2. 키인 경우, keyBit에 저장해준다.  keyBit |= 1<<(map[i][j]-'a');
2. 주어진 key를 keyBit에 더해준다.
3. 주어진 입구에 차례대로 들어간다. 만약 문일 경우, key가 있는 경우에만 입장이 가능하다. bfs(x,y);
   1. 위에서 설명한 조건 분기식에 따라 케이스를 처리해주면 된다.
4. 최종적으로 구한 문서의 갯수(answer)를 출력해준다. 

 

풀이 코드 

import java.io.*;
import java.util.*;

public class Main {
	static int r,c, answer;
	static int keyBit;
	static char[][] map;
	static boolean[][] check;
	static Map<Integer, Queue<int[]>> doorList;
	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));
		int tc = Integer.parseInt(br.readLine());
		
		for(int t=0; t<tc; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			r = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			
			List<int[]> entrance = new ArrayList<>();
			map = new char[r][c];
			keyBit=0;
			answer =0;
			doorList = new HashMap<>();
			for(int i=0; i<r; i++) {
				String line = br.readLine();
				for(int j=0; j<c; j++) {
					map[i][j] = line.charAt(j);
					if(map[i][j] != '*') {
						if(i==0 || i==r-1 || j==0 || j == c-1) {
							if(map[i][j] == '$') {
								answer++;
								map[i][j] ='.';
							}else if('a'<=map[i][j] && map[i][j] <= 'z') {
								keyBit |= 1<<(map[i][j]-'a');
							}
							entrance.add(new int[] {j,i});
						}
					}
				}
			}
			
			char[] keyList = br.readLine().toCharArray();
			for(char key : keyList) {
				if(key=='0') break;
				keyBit |= (1<<(key-'a'));
			}
			check = new boolean[r][c];
			for(int[] pos : entrance) {
				int x = pos[0], y = pos[1];
				if('A' <= map[y][x] && map[y][x] <='Z') {
					int door = 1<<(map[y][x] - 65);
					if((keyBit & door) != door) {
						putDoorQueue(x,y,door);
						continue;
					}
				}
				bfs(x,y);
			}
			System.out.println(answer);
		}
	}
	
	static void bfs(int x, int y){
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] {x,y});
		check[y][x] = true;
		
		while(!q.isEmpty()) {
			int[] p = q.poll();
			int px= p[0];
			int py= p[1];
			
			for(int i=0; i<4; i++) {
				int nx  = px + dx[i];
				int ny  = py + dy[i];
				
				if(nx <0 || ny <0|| nx>c-1 || ny > r-1 || 
						check[ny][nx] || map[ny][nx]=='*') continue;
				
				if(map[ny][nx]=='$') {
					answer++;
				} else if('a' <= map[ny][nx] && map[ny][nx] <= 'z') {
					keyBit |= 1<<(map[ny][nx]-'a');
					for(int door : doorList.keySet()) {
						if((keyBit&door)==door) {
							watingQueueExtract(q, door);
						}
					}
				} else if('A' <= map[ny][nx] && map[ny][nx] <='Z') {
					int door = 1<<(map[ny][nx] - 65);
					if((keyBit & door) != door) {
						putDoorQueue(nx, ny, door);
						continue;
					}
				} 
				check[ny][nx] = true;
				q.add(new int[] {nx,ny});
			}
		}
	}

	private static void watingQueueExtract(Queue<int[]> q, int door) {
		Queue<int[]> waitQueue = doorList.get(door);
		while(!waitQueue.isEmpty()) {
			int[] wq= waitQueue.poll();
			q.add(new int[] {wq[0],wq[1]});
		}
	}

	private static void putDoorQueue(int x, int y, int door) {
		if(doorList.containsKey(door)) {
			doorList.get(door).add(new int[] {x,y});
		}else {
			Queue<int[]> dq = new LinkedList<>();
			dq.add(new int[] {x,y});
			doorList.put(door, dq);
		}
	}
}