[BOJ 9328] 열쇠 (Java)

BOJ 9328 열쇠

문제풀이

재밌는 문제이면서 까다로운 문제였다. 일단 건물 밖으로 나갈수 있다는 조건 때문에 map 배열에 패딩을 줘야해서 입력을 받을 때 조금 까다로웠다. 나머지는 크게 어려운 부분은 없었다. 내가 풀이한 핵심 아이디어는 다음과 같다.

• 키를 습득한 경우에는 (0, 0)에서 다시 시작한다.
• 문서, 키, 문을 습득한(연) 경우에 그 자리를 통로로 바꾼다.

실수로 놓쳤던 부분은 문서, 키, 문을 습득(연) 경우에도 해당 위치를 다시 큐에 넣어서 계속 진행해야한다는 것이였다. 검색해보니 다른 분들은 키와 문을 따로 관리한다거나 큐를 두 개 사용하는 경우도 있었다. 내가 작성한 코드는 뭔가 효율성이 떨어지는 거 같아서 더 좋은 코드를 후에 찾아봐야겠다.

구현코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static class Node {
		int r, c;
		
		Node(int r, int c){
			this.r = r;
			this.c = c;
		}
	}
	
	static Queue<Node> q;
	static HashMap<Character, Character> keys;
	static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	static char[][] map;
	static boolean[][] visited;
	static int T, H, W;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		T = stoi(br.readLine());
		
		for(int t = 0 ; t < T ; ++t) {
			st = new StringTokenizer(br.readLine());
			H = stoi(st.nextToken());
			W = stoi(st.nextToken());
			
			// 건물 밖으로 나갈 수 있기 때문에 map에 패딩을 준다. 
			map = new char[H + 2][W + 2];
			q = new LinkedList<>();
			keys = new HashMap<>();
			
			char[] line;
			for(int r = 1 ; r <= H ; ++r) {
				line = br.readLine().toCharArray();
				for(int c = 1 ; c <= W ; ++c) {
					map[r][c] = line[c - 1];
				}
			}
			
			for(int r = 0 ; r < H + 2 ; ++r) {
				for(int c = 0 ; c < W + 2 ; ++c) {
					if(r == 0 || r == H + 1 || c == 0 || c == W + 1) {
						map[r][c] = '.';
					}
				}
			}
			
			line = br.readLine().toCharArray();
			
			for(int i = 0 ; i < line.length ; ++i) {
				if(line[i] == '0') break;
				// 소문자 -> 대문자 : -32
				// 대문자 -> 소문자 : +32
				keys.put((char)(line[i] - 32), line[i]);
			}
			
			q.offer(new Node(0, 0));
			
			System.out.println(bfs());
		}
	}
	
	private static int bfs() {
		visited = new boolean[H + 2][W + 2];
		visited[0][0] = true;
		int doc = 0;
		boolean flag = false;
		
		while(!q.isEmpty()) {
			Node cur = q.poll();
			
			for(int d = 0 ; d < 4 ; ++d) {
				int nr = cur.r + dir[d][0];
				int nc = cur.c + dir[d][1];
				
				if(nr >= H + 2 || nr < 0 || nc >= W + 2 || nc < 0 ||
						visited[nr][nc] || map[nr][nc] == '*') continue;
				
				switch(map[nr][nc]) {
					// 빈 공간 
					case '.':
						visited[nr][nc] = true;
						q.offer(new Node(nr, nc));
						break;
					// 문서 
					case '$':
						doc++;
						// 먹은 문서 없애기  
						map[nr][nc] = '.';
						visited[nr][nc] = true;
						q.offer(new Node(nr, nc));
						break;
					// 열쇠 또는 문 
					default:
						// 열쇠 
						if(map[nr][nc] >= 'a' && map[nr][nc] <= 'z') {
							// 이미 소유한 키는 신경쓰지 않는다. 
							if(!keys.containsKey(map[nr][nc])) {
								// 키 습득 
								keys.put((char)(map[nr][nc] - 32), map[nr][nc]);
								// 다시 시작 
								flag = true;
							}
							// 먹은 열쇠 없애기 
							map[nr][nc] = '.';
							visited[nr][nc] = true;
							q.offer(new Node(nr, nc));
							
						// 문 
						} else {
							if(keys.containsKey(map[nr][nc])) {
								// 한번 통과한 문은 없애기 
								map[nr][nc] = '.';
								visited[nr][nc] = true;
								q.offer(new Node(nr, nc));
							}
						}
				}
			}
		}
        // 키를 습득했다면 처음 부터 다시 탐색한다.
		if(flag) {
			q.offer(new Node(0, 0));
			doc += bfs();
		}
		
		return doc;
	}

  	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}