문제 링크

성능 요약

메모리: 18984 KB, 시간: 176 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색, 구현

제출 일자

2025년 2월 27일 22:02:23

문제 설명

상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다.

상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.

• '.'는 빈 공간을 나타낸다.
• '*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
• '$'는 상근이가 훔쳐야하는 문서이다.
• 알파벳 대문자는 문을 나타낸다.
• 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.

마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.

상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.

출력

각 테스트 케이스 마다, 상근이가 훔칠 수 있는 문서의 최대 개수를 출력한다.

풀이

느낀점

• 조금 까다로운 구현문제였다.
• 초기화 부분에서 진입 가능한 부분을 놓쳐서 질문게시판을 참고한 점이 아쉽다.
• 간단한 테케라도 직접 몇개 만들어봤으면 찾을 수 있지 않았을까 싶다.
• 시간을 재면서 집중해서 풀어보는 것이 좋을 것 같다. 무제한으로 여유롭게 푸니까 정확히 얼마나 걸렸는지 잘 모르겠다.

설계 : 20분

• 알파벳이 26개이기 때문에 2^26 으로 표현 가능해서 가지고 있는 열쇠들의 상태는 정수로 표현하기로 했다.
• 열쇠를 찾기 전에 문을 발견하면 Map<Integer, List<int[]>> lockedDoors 에 저장하기로 했다.
  • key: 문에 맞는 키 알파벳을 0~25까지 표현했을때의 인덱스, value: 문의 위치
• 방문처리를 boolean[][] 으로 해줬다.
• map 입력시에 진입 가능한 부분을 queue에 추가하고, 문이나 키일 경우 알맞게 처리하고 저장(메서드)하도록 했다.
• 입력된 키를 모두 저장한다.
  • 진입 가능한 부분을 맵 입력시에 추가했기 때문에 키가 입력된 후에 진입 가능한 부분을 고려하지 못해 1차에 틀렸다.
  • 키를 입력하면서 lockedDoors 를 순회해 진입가능한 부분을 찾아야 한다.
• queue가 빌때까지 bfs를 계속하며 $를 센다.

코드(Java)

• 구현 시간: 80분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 열쇠_문제번호
 * Date: 2025.02.27
 */

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

public class Main {
	static int[] dr = {-1, 0, 1, 0};
	static int[] dc = {0, 1, 0, -1};
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static int keys;
	static Map<Integer, List<int[]>> lockedDoors;
	static boolean[][] visited;
	static char[][] map;
	static Queue<int[]> queue;
	static final int DOOR_TO_KEY = -65;
	static final int KEY_TO_KEY = -97;
	static final int KEY_TO_DOOR = 65;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = Integer.parseInt(br.readLine());

		for (int tc = 0; tc < T; tc++) {

			String[] input = br.readLine().split(" ");
			int n = Integer.parseInt(input[0]);
			int m = Integer.parseInt(input[1]);

			map = new char[n+2][m+2];
			visited = new boolean[n+2][m+2];
			lockedDoors = new HashMap<>();
			keys = 0;
			queue = new ArrayDeque<>();

			// map을 입력, 안팎을 드나들 수 있는 곳(시작점) 저장
			for (int i = 1; i <= n; i++) {
				char[] tmp = br.readLine().toCharArray();
				for (int j = 1; j <= m; j++) {
					map[i][j] = tmp[j-1];
					if ((i == 1 || j == 1 || i == n || j == m) && map[i][j] != '*') {
						check(i, j);
					}
				}
			}

			char[] keyInput = br.readLine().toCharArray();
			if (keyInput[0] != '0') {
				for (char k : keyInput) {
					int key = k + KEY_TO_KEY;
					open(key);
					keys |= (1 << key);
				}
			}

			int answer = 0;
			while (!queue.isEmpty()) {

				int[] curr = queue.poll();
				if (map[curr[0]][curr[1]] == '$') answer++;

				for (int d = 0; d < 4; d++) {
					int nr = curr[0] + dr[d];
					int nc = curr[1] + dc[d];

					if (visited[nr][nc] || map[nr][nc] == '\u0000' || map[nr][nc] == '*') continue;
					check(nr, nc);
				}
			}

			bw.write(String.valueOf(answer) + "\n");
		}

		bw.flush();
		bw.close();
		br.close();
	}

	public static void check(int r, int c) {
		// 문인데 열쇠가 없으면 잠긴 문 리스트에 추가
		if (map[r][c] >= 65 && map[r][c] <= 90
				&& (keys & (1 << (map[r][c] + DOOR_TO_KEY))) == 0) {
			List<int[]> doors = lockedDoors.getOrDefault(map[r][c] + DOOR_TO_KEY, new ArrayList<>());
			doors.add(new int[] {r, c});
			lockedDoors.put(map[r][c] + DOOR_TO_KEY, doors);
			visited[r][c] = true;
			return;

		// 키인데
		} else if (map[r][c] >= 97 && map[r][c] <= 122) {
			int key = map[r][c] + KEY_TO_KEY;
			// 처음 발견한 키면 지금까지 방문한 문 중에 맞는 문이 있는지 확인
			if ((keys & (1 << key)) == 0) open(key);
			// 키 추가
			keys |= (1 << key);
		}
		queue.add(new int[] {r, c});
		visited[r][c] = true;
	}

	public static void open(int keyIdx) {
		List<int[]> doors = lockedDoors.getOrDefault(keyIdx, new ArrayList<>());
		int door = keyIdx + KEY_TO_DOOR;
		for (int[] d : doors) {
			if (map[d[0]][d[1]] == door) queue.add(d);
		}
	}
}