백준 9328 : 열쇠

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

9328번: 열쇠

[ 문제풀이 ]

bfs + set을 활용하면 해결할 수 있는 문제이다.

Key의 종류가 최대 26개이기 때문에 이를 비트로 표현하려면 2^26(67108864)만큼의 공간이 필요하다. 이는 쓸데없는 메모리를 많이 사용하기 때문에 set을 이용해서 관리해주도록 하자.

또한, 시작점을 어디부터 시작하느냐에 따라서 얻을 수 있는 문서의 개수가 달라지기 때문에 한 번의 탐색으로 처리할 수는 없다.

따라서 아직 발견하지 못한 Key를 찾을 때마다 즉시 탐색을 종료해주고 처음부터 다시 탐색하도록 구현해준다. 이렇게 하면 이전에 갈 수 없었던 곳도 갈 수 있게 되기 때문이다.

Map이 최대 100x100이고, Key의 종류가 최대 26개이기 때문에 Key를 찾을 때마다 반복하여도 충분한 시간이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {

	static class Node {
		int y, x;
		Node (int y, int x) {
			this.y = y;
			this.x = x;
		}
	}
	
	static int h, w, count;
	static char[][] map;
	static boolean[][] visit;
	static Set<Character> keys;
	static Queue<Node> q;
	static boolean find;
    
	static int[][] dir = {{-1,0},{1,0},{0,1},{0,-1}};
	
	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			int T = Integer.parseInt(br.readLine());
			map = new char[101][101];
			visit = new boolean[101][101];
			keys = new HashSet<>();
			q = new LinkedList<>();
            
			while (T-- > 0) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				h = Integer.parseInt(st.nextToken());
				w = Integer.parseInt(st.nextToken());
				for (int i = 0; i < h; ++i) {
					String input = br.readLine();
					for (int j = 0; j < w; ++j) {
						map[i][j] = input.charAt(j);
					}
				}
				String key = br.readLine();
				for (int i = 0; i < key.length(); ++i) {
					keys.add(key.charAt(i));
				}
				
				//모든 외벽을 시작점으로 탐색
				//탐색 도중 아직 발견하지 못한 Key를 찾으면
				//즉시, 탐색을 종료하고 처음부터 다시 탐색
				do {
					find = false;
					for (int i = 0; i < h; ++i) Arrays.fill(visit[i], false);

					for (int i = 0; i < w; ++i) {
						if (visit[0][i] || map[0][i] == '*') continue;
						bfs(0, i);
						if (find) break;
					}
					if (find) continue;
                    
					for (int i = 0; i < w; ++i) {
						if (visit[h - 1][i] || map[h - 1][i] == '*') continue;
						bfs(h - 1, i);
						if (find) break;
					}
					if (find) continue;
					
					for (int i = 0; i < h; ++i) {
						if (visit[i][0] || map[i][0] == '*') continue;
						bfs(i, 0);
						if (find) break;
					}
					if (find) continue;
					
					for (int i = 0; i < h; ++i) {
						if (visit[i][w - 1] || map[i][w - 1] == '*') continue;
						bfs(i, w - 1);
						if (find) break;
					}
				} while (find);
				bw.write(count + "\n");
				q.clear();
				keys.clear();
				count = 0;
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	public static void bfs(int y, int x) {
		q.clear();
		q.offer(new Node(y, x));
		visit[y][x] = true;
		
		//시작점 판별
		if (map[y][x] == '$') {
			count++;
			map[y][x] = '.';
		} else if (Character.isLowerCase(map[y][x])) {
			if (!keys.contains(map[y][x])) {
				keys.add(map[y][x]);
				map[y][x] = '.';
				find = true;
				return;
			}
		} else if (Character.isUpperCase(map[y][x])) {
			char key = (char)((int)map[y][x] + 32);
			if (keys.contains(key)) {
				map[y][x] = '.';
			} else {
				return;
			}
		}
		
		while (!q.isEmpty()) {
			Node n = q.poll();
			
			for (int d = 0; d < 4; ++d) {
				int ny = n.y + dir[d][0];
				int nx = n.x + dir[d][1];
				
				if (ny < 0 || nx < 0 || ny >= h || nx >= w) continue;
				if (map[ny][nx] == '*' || visit[ny][nx]) continue;
				visit[ny][nx] = true;
				
				if (map[ny][nx] == '.') {
					q.offer(new Node(ny, nx));
					continue;
				}
				
				if (map[ny][nx] == '$') {
					count++;
					map[ny][nx] = '.';
					q.offer(new Node(ny, nx));
					continue;
				}
				
				if (Character.isLowerCase(map[ny][nx])) {
					if (!keys.contains(map[ny][nx])) {
						keys.add(map[ny][nx]);
						map[ny][nx] = '.';
						find = true;
						return;
					}
					map[ny][nx] = '.';
					q.offer(new Node(ny, nx));
					continue;
				}
				
				if (Character.isUpperCase(map[ny][nx])) {
					char key = (char)((int)map[ny][nx] + 32);
					if (keys.contains(key)) {
						map[ny][nx] = '.';
						q.offer(new Node(ny, nx));
					}
				}
			}
		}
	}
}