[Gold I] 열쇠 - 9328
성능 요약
메모리: 22360 KB, 시간: 184 ms
분류
너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal), 구현(implementation)
문제 설명
상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다.
상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.
각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.
- '.'는 빈 공간을 나타낸다.
- '*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
- '$'는 상근이가 훔쳐야하는 문서이다.
- 알파벳 대문자는 문을 나타낸다.
- 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.
마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.
상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.
출력
각 테스트 케이스 마다, 상근이가 훔칠 수 있는 문서의 최대 개수를 출력한다.
풀이
테스트케이스는 https://gooddaytocode.blogspot.com/2017/03/benelux-algorithm-programming-contest.html 에서 확인할 수 있다.
꽤 까다로운 구현 + 그래프 문제였다.
처음에는 bfs를 통해 각각 방문처리를 하면 된다고 생각했는데, 이미 방문한 곳이어도 새로운 문이 열리면 다시 방문할 가능성이 있어서 처음 생각한 방향이 잘못되었음을 알게 되었다.
생각해낸 로직은 다음과 같다.
- 문이 아닌 경우에 처음 방문할 수 있는 곳(가장자리)을 모두 방문한다.
- 문 중에서 방문할 수 있는 곳을 방문한다. (가장자리 또는 가장자리와 인접해서 방문 가능한 곳)
**방문할 수 있는 문이란,
- 가장자리에 위치
- 열쇠가 있음
- 인접한 곳을 이미 방문했음
을 의미한다.
bfs를 통해 방문할 수 있는 곳을 계속 방문하는데, 방문한 곳의 상태에 따라 구분 가능하다.
- 빈 곳: 방문 후 queue에 그대로 추가
- 문서($): 방문 후 ans 1 증가
- 열쇠(소문자): 방문 후, queue에서 poll한 후, 해당 열쇠로 열 수 있는 문이 있을 경우 문을 열고, 큐에 추가
- 문: 방문 후 door 리스트에서 제거 (조금이라도 효율성을 높이기 위해)
테스트케이스를 통해 잘못된 로직들을 찾았는데, 여러 경우가 있었다.
열쇠에 대해 방문 처리를 queue에 추가하기 전에 해서, 방문이 불가능한 문인데도 방문이 가능하다고 인식하는 경우가 있었다. 그래서 queue에서 poll한 후에 가능한 문들을 추가하였다.
처음에는 문만 queue에 추가하다가, 문을 열고 다시 다른 곳들을 이어서 방문해야 하는 경우가 생겨서 일반적인 bfs 로직으로 변경하였다.
또 문에 대해 열쇠만 있으면 열 수 있다고 판단해서, 인접한 곳을 이미 방문한 후거나 문이 가장자리에 있을 경우에만 이동 가능하다는 사실도 빼먹었다.
여러 가지 조건들을 확인하는 게 까다로운 구현 문제인 것 같다.
package BOJ.Gold.g1;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BOJ_9328_열쇠 {
static class Door {
int idx; // 알파벳 순서
int r;
int c;
public Door(int idx, int r, int c) {
this.idx = idx;
this.r = r;
this.c = c;
}
}
static int N, M;
static char[][] map;
static boolean[][] visited;
static int ans;
static boolean[] key;
static int[] dr = {1, -1, 0, 0};
static int[] dc = {0, 0, 1, -1};
static List<Door> doors;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
while (T-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new char[N][M];
visited = new boolean[N][M]; // 방문 표시
ans = 0;
key = new boolean[26];
doors = new ArrayList<>();
for (int i = 0; i < N; i++) {
String input = br.readLine();
for (int j = 0; j < M; j++) {
map[i][j] = input.charAt(j);
if (map[i][j] >= 'a' && map[i][j] <= 'z' && (i == 0 || j == 0 || i == N - 1 || j == M - 1))
key[map[i][j] - 'a'] = true; // 가장 자리 처리
if (map[i][j] >= 'A' && map[i][j] <= 'Z')
doors.add(new Door(map[i][j] - 'A', i, j));
}
}
String keys = br.readLine();
if (!keys.equals("0")) {
int length = keys.length();
for (int i = 0; i < length; i++) {
int val = keys.charAt(i) - 'a';
if (!key[val]) {
key[keys.charAt(i) - 'a'] = true;
}
}
}
Queue<int[]> doorQueue = new LinkedList<>();
// 가장자리에서 입구에 추가될 수 있는 것 추가하기
for (int i = 0; i < N; i++) {
if (map[i][0] == '.' || map[i][0] == '$' || (map[i][0] >= 'a' && map[i][0] <= 'z')) {
doorQueue.add(new int[]{i, 0});
}
if (map[i][M - 1] == '.' || map[i][M - 1] == '$' || (map[i][M - 1] >= 'a' && map[i][M - 1] <= 'z')) {
doorQueue.add(new int[]{i, M - 1});
}
}
for (int j = 0; j < M; j++) {
if (map[0][j] == '.' || map[0][j] == '$' || (map[0][j] >= 'a' && map[0][j] <= 'z')) {
// 빈 공간이거나, 문서이거나, 열쇠이거나, 문인데 열쇠가 있거나
doorQueue.add(new int[]{0, j});
}
if (map[N - 1][j] == '.' || map[N - 1][j] == '$' || (map[N - 1][j] >= 'a' && map[N - 1][j] <= 'z')) {
// 빈 공간이거나, 문서이거나, 열쇠이거나, 문인데 열쇠가 있거나
doorQueue.add(new int[]{N - 1, j});
}
}
// 문 차례로 열기
for (Door door : doors) {
if (key[door.idx]) {
// 문이면 인접한 곳 중에서 이미 방문한 곳이 있을 때만 queue에 추가함
if (checkDoor(door.r, door.c))
doorQueue.add(new int[]{door.r, door.c}); //
}
}
while (!doorQueue.isEmpty()) {
int[] arr = doorQueue.poll();
int r = arr[0];
int c = arr[1];
if (visited[r][c]) continue;
visited[r][c] = true;
if (map[r][c] >= 'A' && map[r][c] <= 'Z') {
for (Door d : doors) // 문 리스트에서 제거하기
if (d.r == r && d.c == c) {
doors.remove(d);
break;
}
}
if (map[r][c] >= 'a' && map[r][c] <= 'z') { // 열쇠
key[map[r][c] - 'a'] = true;
for (Door tmp : doors) { // 열 수 있는 문을 연다
if (!visited[tmp.r][tmp.c] && tmp.idx == map[r][c] - 'a' && checkDoor(tmp.r, tmp.c)) {
doorQueue.add(new int[]{tmp.r, tmp.c});
}
}
}
if (map[r][c] == '$') {
ans++;
}
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (nr >= 0 && nr < N && nc >= 0 && nc < M && map[nr][nc] != '*' && !visited[nr][nc]) {
if (map[nr][nc] >= 'a' && map[nr][nc] <= 'z' || map[nr][nc] == '$' || map[nr][nc] == '.') { // 열쇠, 빈 공간, 문서
doorQueue.add(new int[]{nr, nc});
} else if (map[nr][nc] >= 'A' && map[nr][nc] <= 'Z') // 문
if (key[map[nr][nc] - 'A']) { // 열 수 있는 경우에만
doorQueue.add(new int[]{nr, nc});
}
}
}
}
sb.append(ans).append("\n");
}
System.out.print(sb);
}
static boolean checkDoor(int r, int c) {
if (r == 0 || r == N - 1 || c == 0 || c == M - 1) return true; // 가장자리는 무조건 가능
for (int d = 0; d < 4; d++) {
int nr = r + dr[d];
int nc = c + dc[d];
if (nr >= 0 && nr < N && nc >= 0 && nc < M && visited[nr][nc])
return true;
}
return false;
}
}
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 5052 - 전화번호 목록 (0) | 2023.01.09 |
---|---|
[백준] 2533 - 사회망 서비스(SNS) (자바 Java) (0) | 2023.01.07 |
[백준] 2166 - 다각형의 면적 (자바 Java) (0) | 2023.01.02 |
[백준] 1005 - ACM Craft (자바 Java) (0) | 2022.12.27 |
[백준] 2493 - 탑 (자바 Java) (1) | 2022.12.23 |