백준 9328번 : 열쇠 [Java]

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

문제 탐색하기

문제는 상근이가 h * w의 지도에서 열쇠와 문을 통해서 원하는 문서를 찾도록 구현하면 된다. 자칫 까다로워 보일 수 있는데 몇가지를 잘 생각해보면 비교적 구현하기 어렵지 않을 수 있다. 먼저 어떤 식으로 처리해야할지 떠올려보자. 입구는 여러 개일 수 있기 때문에 모든 입구를 매번 다 탐색할 수는 없다.

 

이에 따라서 테두리에 빈 칸을 두어서 항상 같은 빈칸에서 시작하도록 구현하면 된다. 이러면 입구를 찾는 방법을 떠올리지 않아도 되고 그저 bfs를 통해서 열린 부분을 탐색하면 된다. 예제 입력의 첫번째 테스트 케이스를 예로 들자면 아래와 같다.

 

*****************
.............**$*
*B*A*P*C**X*Y*.X.
*y*x*a*p**$*$**$*
*****************

// 테두리를 빈칸으로 둘러싸기

...................
.*****************.
..............**$*.
.*B*A*P*C**X*Y*.X..
.*y*x*a*p**$*$**$*.
.*****************.
...................

 

위처럼 테두리를 두르고 (0, 0)부터 항상 시작하도록 하면 모든 입구를 찾을 수 있게 된다. 나머지는 문제의 조건에 맞게 갖고 있는 키를 통해서 문을 열 수 있도록 구현하고, 문을 열고, 문서를 찾는 부분을 구현하면 된다. 이 때 키, 문, 문서를 찾고 성공적으로 취득하거나 열 수 있다면 해당 부분을 다시 빈 칸으로 만들면 된다.

 

그러면 bfs를 몇 번이나 반복 해야할까? while문을 통해서 무한대로 돌린다고 하더라도 답은 늘어나지 않는다. 이에 따라서 탈출 조건을 지정해야하는데, 이는 다음과 같이 설계할 수 있다.

 

첫번 째 bfs를 돌리고 나서부터 지도의 복사본을 저장한다. 이 때 그 다음 번의 bfs의 결과 지도와 이전의 복사본이 동일하다면 사이클이 존재한다고 볼 수 있다. 이를 이용해서 탈출조건을 만들면 된다.

 

코드 구현하기

1. 입력을 처리하고 2차원 배열을 통해서 지도를 구현한다.
2. 모든 테스트케이스에 대하여 아래와 같이 bfs를 구현한다.
   
   1. 현재 가지고 올 수 있는 문서를 찾는다.
   2. 현재 취득할 수 있는 키를 찾는다.
   3. 현재 갖고 있는 키를 통해 열 수 있는 문을 찾는다.
   4. 위에서 설명한 탈출조건이 성립하는지 확인하고 탈출한다.
3. 모든 답을 한번에 출력한다.

풀이

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

public class Main {
	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}
	}

	static int TC;
	static char[][] map;
	static char[][] control;
	static boolean[][] visited;
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, -1, 0, 1};
	static HashSet<Character> keys = new HashSet<>();

	static boolean isKey(char c) {
		return Character.isLowerCase(c);
	}

	static boolean isDoor(char c) {
		return Character.isUpperCase(c);
	}

	static boolean isDocument(char c) {
		return c == '$';
	}

	static class Node {
		int x, y;

		public Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	static boolean isCycle(int h, int w) {
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (map[i][j] != control[i][j]) {
					return false;
				}
			}
		}
		return true;
	}

	static void copy(int h, int w) {
		control = new char[h][w];
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				control[i][j] = map[i][j];
			}
		}
	}

	static int bfs(int h, int w) {
		visited = new boolean[h][w];
		visited[0][0] = true;
		int docs = 0;
		LinkedList<Node> q = new LinkedList<>();
		q.add(new Node(0, 0));
		while (!q.isEmpty()) {
			Node now = q.poll();

			for (int i = 0; i < 4; i++) {
				int nx = now.x + dx[i];
				int ny = now.y + dy[i];

				if (nx < 0 || ny < 0 || nx >= h || ny >= w || visited[nx][ny] || map[nx][ny] == '*') {
					continue;
				}

				if (map[nx][ny] == '.') {
					visited[nx][ny] = true;
					q.add(new Node(nx, ny));
				} else if (isDoor(map[nx][ny])) {
					if (keys.contains(Character.toLowerCase(map[nx][ny]))) {
						visited[nx][ny] = true;
						q.add(new Node(nx, ny));
						map[nx][ny] = '.';
					}
				} else if (isKey(map[nx][ny])) {
					keys.add(map[nx][ny]);
					map[nx][ny] = '.';
					visited[nx][ny] = true;
					q.add(new Node(nx, ny));
				} else if (isDocument(map[nx][ny])) {
					docs++;
					map[nx][ny] = '.';
					visited[nx][ny] = true;
					q.add(new Node(nx, ny));
				}
			}
		}
		return docs;
	}

	public static void main(String[] args) {
		FastReader fr = new FastReader();
		TC = fr.nextInt();
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < TC; i++) {
			int h = fr.nextInt();
			int w = fr.nextInt();
			map = new char[h + 2][w + 2];
			for (int j = 0; j < h + 2; j++) {
				Arrays.fill(map[j], '.');
			}

			for (int j = 0; j < h; j++) {
				String line = fr.next();
				for (int k = 0; k < w; k++) {
					map[j + 1][k + 1] = line.charAt(k);
				}
			}

			String key = fr.next();
			for (int j = 0; j < key.length(); j++) {
				if (Character.isDigit(key.charAt(j))) {
					continue;
				}
				keys.add(key.charAt(j));
			}

			int answer = 0;

			while (true) {

				int result = bfs(h + 2, w + 2);
				if (result == 0 && keys.isEmpty()) {
					break;
				} else {
					answer += result;
				}
				if (control != null) {
					if (isCycle(h + 2, w + 2)) {
						break;
					}
				}

				copy(h + 2, w + 2);
			}

			sb.append(answer + "\n");
			control = null;
			keys.clear();
		}

		System.out.println(sb);
	}
}