BOJ 9328 열쇠(Java)
문제 탐색하기
- 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다.
- 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다.
- 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다.
- 상근이는 상하좌우로만 이동할 수 있다.
상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.
각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.
- ’.’는 빈 공간을 나타낸다.
- ‘*‘는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
- ’$’는 상근이가 훔쳐야하는 문서이다.
- 알파벳 대문자는 문을 나타낸다.
- 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.
-
마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 “0”이 주어진다.
- 상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다.
- 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다.
- 열쇠는 여러 번 사용할 수 있다.
출력
각 테스트 케이스에 대해서, 상근이가 훔칠 수 있는 문서의 최대 개수를 출력한다.
예제 입력
3
5 17
*****************
.............**$*
*B*A*P*C**X*Y*.X.
*y*x*a*p**$*$**$*
*****************
cz
5 11
*.*********
*...*...*x*
*X*.*.*.*.*
*$*...*...*
***********
0
7 7
*ABCDE*
X.....F
W.$$$.G
V.$$$.H
U.$$$.J
T.....K
*SQPML*
irony
예제 출력
3
1
0
코드 설계하기
구현 방법
- BFS를 사용하여 탐색할 수 있는 모든 영역을 탐색한다.
- 가장자리에서 시작할 수 있는 모든 위치를 찾아 큐에 넣는다.
- 열쇠를 획득하면 해당 열쇠를 사용할 수 있는 문들을 다시 탐색 가능하게 한다.
- 문서를 찾을 때마다 카운트를 증가시킨다.
- 새로운 열쇠를 찾으면, 이전에 해당 열쇠가 필요한 문 때문에 방문하지 못했던 위치들을 다시 탐색한다.
시간 복잡도
- 각 칸을 최대 1번만 방문하므로 O(h*w)
- 열쇠를 새로 발견할 때마다 전체 맵을 다시 확인해야 할 수 있어서, 최악의 경우 O(26hw)
- 전체 시간 복잡도는 O(h*w)
시도 회차 별 수정사항(Optional)
- 1차 시도: 초기 BFS 구현. 가장자리 처리 및 일반 BFS 탐색 로직 포함.
- 2차 시도 (수정): BFS 탐색 중 문서를 발견(
$)했을 때,documents++만 하고 해당 위치를 ‘.’으로 변경하지 않아 중복 카운트 가능성이 있었음. BFS 내부 로직에서if (map[nx][ny] == '$')블록 안에map[nx][ny] = '.';를 추가하여 해결.
문서를 이미 발견한 경우 중복 처리를 고려해야 했다… 🤥
정답 코드 (Java)
package BFS;
import java.io.*;
import java.util.*;
public class b9328 {
private static int h, w;
private static char[][] map;
private static boolean[][] visited;
private static boolean[] keys;
private static List<int[]>[] doors;
private static int[] dx = {-1, 1, 0, 0};
private static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
while (T-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
h = Integer.parseInt(st.nextToken());
w = Integer.parseInt(st.nextToken());
map = new char[h][w];
visited = new boolean[h][w];
keys = new boolean[26]; // a-z
doors = new ArrayList[26]; // A-Z
for (int i = 0; i < 26; i++) {
doors[i] = new ArrayList<>();
}
// 지도 입력
for (int i = 0; i < h; i++) {
String line = br.readLine();
for (int j = 0; j < w; j++) {
map[i][j] = line.charAt(j);
}
}
// 초기 열쇠 설정
String initialKeys = br.readLine();
if (!initialKeys.equals("0")) {
for (char key : initialKeys.toCharArray()) {
keys[key - 'a'] = true;
}
}
bw.write(bfs() + "\n");
bw.flush();
}
bw.close();
}
private static int bfs() {
Queue<int[]> q = new LinkedList<>();
int documents = 0;
// 가장자리 위치를 시작점으로 확인
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if ((i == 0 || i == h - 1 || j == 0 || j == w - 1) && map[i][j] != '*') {
if (map[i][j] >= 'A' && map[i][j] <= 'Z') {
// 문인 경우 열쇠가 있는지 확인
int door = map[i][j] - 'A';
if (keys[door]) {
q.offer(new int[]{i, j});
visited[i][j] = true;
} else {
doors[door].add(new int[]{i, j});
}
} else {
// 문이 아닌 경우 바로 시작점으로 추가
if (map[i][j] == '$') {
documents++;
map[i][j] = '.';
} else if (map[i][j] >= 'a' && map[i][j] <= 'z') {
int key = map[i][j] - 'a';
keys[key] = true;
// 해당 열쇠로 열 수 있는 문들 큐에 추가
for (int[] door : doors[key]) {
q.offer(door);
visited[door[0]][door[1]] = true;
}
doors[key].clear();
}
q.offer(new int[]{i, j});
visited[i][j] = true;
}
}
}
}
// BFS 탐색
while (!q.isEmpty()) {
int[] current = q.poll();
int x = current[0];
int y = current[1];
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx >= 0 && nx < h && ny >= 0 && ny < w && !visited[nx][ny] && map[nx][ny] != '*') {
if (map[nx][ny] >= 'A' && map[nx][ny] <= 'Z') {
// 문인 경우
int door = map[nx][ny] - 'A';
if (keys[door]) {
visited[nx][ny] = true;
q.offer(new int[]{nx, ny});
} else {
doors[door].add(new int[]{nx, ny});
}
} else {
visited[nx][ny] = true;
if (map[nx][ny] == '$') {
// 문서 발견
documents++;
map[nx][ny] = '.';
} else if (map[nx][ny] >= 'a' && map[nx][ny] <= 'z') {
// 열쇠 발견
int key = map[nx][ny] - 'a';
if (!keys[key]) {
keys[key] = true;
// 해당 열쇠로 열 수 있는 문들 큐에 추가
for (int[] door : doors[key]) {
q.offer(door);
visited[door[0]][door[1]] = true;
}
doors[key].clear();
}
}
q.offer(new int[]{nx, ny});
}
}
}
}
return documents;
}
}
Leave a comment