문제
https://www.acmicpc.net/problem/9328
입력
-
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.
-
각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w 가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.
출력
- 각 테스트 케이스 마다, 상근이가 훔칠 수 있는 문서의 최대 개수를 출력한다.
풀이
제한조건
- (2 ≤ h, w ≤ 100)
접근방법
탐색
단순 탐색이다. 시간에 조금 유의하며 진행해보자.
문제에서 가장 주의해야할 점은, 각 타입의 문이 여러개일 수 있다는 것과, 열쇠 또한 여러개일 수 있다는 것이다.
따라서 내가 가지고 있는 열쇠가 무엇인가를 표현하기 위해 Set 자료구조를,
발견한 문에 대해서 각 문의 위치정보를 모두 저장하도록 하자.
이외의 부분은 단순 시뮬레이션 이므로 아래와 같이 순서를 정하고 차근차근 진행하면 된다.
진행 순서는 다음과 같다.
1. 외곽선을 순회하며 Queue에 모두 넣는다.
2. Queue의 각 원소에 대해 탐색을 진행한다.
a. 벽이라면, 다음 원소로 진행.
b. 현재위치가 문이라면, 위치를 기록하고 열쇠의 유무에 따라 탐색 또는 생략
c. 현재 위치가 문서가 있는 곳이라면, result++
d. 현재 칸이 열쇠가 있다면, 열쇠를 추가하고, 대응하는 문의 위치를 Queue에 추가.
e. 현재 위치로 부터 4방향 탐색.문과 열쇠를 set으로 관리하면서 대소문자 관리에 주의한다면 쉽게 해결할 수 있다.
읽어도 잘 모르겠다면, 시뮬레이션 문제이기에 별도의 설명없이 위의 순서와 코드의 주석을 참고해보자..!
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.stream.Collectors;
public class Main {
static int H, W;
static char[][] arr;
static boolean[][] visit;
static Set<Character> key;
final static int EMPTY_SPACE = 0;
final static int WALL = 1;
final static int DOCUMENT = 2;
final static int DOOR = 3;
final static int KEY = 4;
static int[] dx = {1, -1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader((System.in)));
int T = stoi(in.readLine());
for (int tc = 0; tc < T; ++tc) {
String[] inputs = in.readLine().split(" ");
H = stoi(inputs[0]);
W = stoi(inputs[1]);
arr = new char[H][W];
visit = new boolean[H][W];
for (int i = 0; i < H; ++i)
arr[i] = in.readLine().toCharArray();
key = new HashSet<>();
setKey(in.readLine());
simulation();
}
System.out.println(sb);
}
private static void setKey(String s) {
if (s.equals("0"))
return;
for (int i = 0; i < s.length(); ++i)
key.add(s.charAt(i));
}
private static void simulation() {
int result = 0; // 발견한 전체 문서의 수
Queue<int[]> q = new ArrayDeque<>(); // 탐색용 Queue
// 외곽선을 순회하며 시작하자.
for (int i = 0; i < W; ++i) {
q.add(new int[] {0, i});
q.add(new int[] {H - 1, i});
visit[0][i] = true;
visit[H - 1][i] = true;
}
for (int i = 1; i < H - 1; ++i) {
q.add(new int[] {i, 0});
q.add(new int[] {i, W - 1});
visit[i][0] = true;
visit[i][W - 1] = true;
}
Map<Character, Set<List<Integer>>> doorPos = new HashMap<>();
// 본격적인 탐색.
while (!q.isEmpty()) {
int[] cur = q.poll();
int x = cur[0];
int y = cur[1];
char c = arr[x][y];
int type = getType(c);
// 외곽선을 넣는 과정에서 벽이 있을 수 있다. 벽은 탐색 불가.
if (type == WALL)
continue;
// 현재 위치가 문이 있는 위치인 경우
if (type == DOOR) {
char lowerCase = Character.toLowerCase(c);
// 처음보는 문이라면, 위치를 기록한다.
Set<List<Integer>> posList = doorPos.getOrDefault(lowerCase, new HashSet<>());
posList.add(Arrays.stream(cur).boxed().collect(Collectors.toList()));
doorPos.put(lowerCase, posList);
// 열쇠가 없다면, 더이상 진행할 수 없다.
if (!key.contains(lowerCase))
continue;
}
// 현재 칸이 문서가 있는 곳
if (type == DOCUMENT)
result++;
// 현재 칸이 열쇠가 있는 곳
if (type == KEY) {
key.add(c); // 열쇠 추가
// 대응하는 문을 본적이 있다면, 해당 위치부터 재탐색 한다.
if (doorPos.containsKey(c))
for (List<Integer> iter : doorPos.get(c))
q.add(new int[] {iter.get(0), iter.get(1)});
}
// 상하좌우 중 갈 수 있는 방향에 대해서 탐색을 진행한다.
for (int d = 0; d < 4; ++d) {
int nx = x + dx[d];
int ny = y + dy[d];
// 범위 내부이면서 가본적 없는 곳
if (isInRange(nx, ny) && !visit[nx][ny] && arr[nx][ny] != WALL) {
visit[nx][ny] = true;
q.add(new int[] {nx, ny});
}
}
}
sb.append(result).append("\n");
}
private static int getType(char c) {
if (c == '.')
return EMPTY_SPACE;
if (c == '*')
return WALL;
if (c == '$')
return DOCUMENT;
if ('A' <= c && c <= 'Z')
return DOOR;
if ('a' <= c && c <= 'z')
return KEY;
return -1;
}
private static boolean isInRange(int x, int y) {
if (0 <= x && x < H && 0 <= y && y < W)
return true;
return false;
}
private static int stoi(String s) {
return Integer.parseInt(s);
}
}