[문제 바로가기] https://www.acmicpc.net/problem/9328
📌문제 설명
상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다.
상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.
- '.'는 빈 공간을 나타낸다.
- '*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
- '$'는 상근이가 훔쳐야하는 문서이다.
- 알파벳 대문자는 문을 나타낸다.
- 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.
마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.
상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 빈 공간이나 문을 통해 빌딩 안팎을 드나들 수 있다. 각각의 문에 대해서, 그 문을 열 수 있는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.
출력
각 테스트 케이스 마다, 상근이가 훔칠 수 있는 문서의 최대 개수를 출력한다.
💡 문제 풀이
주어진 지도(2차원 배열 - w x h)를 탐색하여 훔칠 수 있는 문서('$')를 찾는 간단한 문제처럼 보이지만 문제를 해결하기 위해서 아래의 두 가지를 주의해야 했다.
-
지도의 출입은 빌딩 가장자리의 빈 공간이나 열쇠로 열 수 있는 문이다.
-
이동 중에 바닥에 놓여진 열쇠를 획득하여 추가로 문을 열 수 있다.
1번문제 해결
먼저 1번을 해결하기 위해서는 주어진 지도의 테두리에 빈 공간 '.'을 추가하였다.
물론, 가장자리에서 빈 공간을 찾아 탐색할 수도 있지만 테두리에 빈 공간들을 추가하게되면 기존의 지도에서 가장자리의 빈 공간을 찾을 필요가 없어진다. → 단순히 (0, 0)부터 탐색을 시작하면 자연스럽게 빈 공간을 지나가게 된다.
2번문제 해결
(개인적으로) 2번의 문제가 간단하지 않았다.(by 시간 초과)
탐색을하면서 열쇠를 습득하여 새로운 문을 열 수 있지만, 문제는 벽에 둘러싸인 문은 열어도 갈 수 없기 때문에 이것을 구분지어야 했다.
→ 열쇠로 열 수 있는 문이 벽에 둘러싸인 공간이라면 상근이는 해당 공간으로 이동할 수 없다.
해결한 방법은 visited의 초기화 였다.
우선 주어진 열쇠들로 열 수 있는 문을 모두 연다. (= 빈 공간('.')으로 바꾼다.)
이후 BFS를 진행한다.
만약, 새로운 열쇠를 습득하였다면? 다시 해당 열쇠로 열 수 있는 문을 모두 연다.
그리고 다시 BFS를 탐색하는데 이 때 visited를 초기화하여 새롭게 탐색한다.
visited를 초기화하면 이전에 진행했던 BFS를 반복 진행하지만 벽에 둘러 싸인 문을 열어도 해당 공간은 지나가지 않기 때문에 앞서 제기한 문제는 해결된다.
코드는 다음과 같다.
import sys
from collections import deque
d = [(-1, 0), (1, 0), (0, 1), (0, -1)]
def unlock(): # 주어진(또는 획득한) 열쇠로 문을 여는 작업
for r in range(h+2):
for c in range(w+2):
if maps[r][c].lower() in keys:
maps[r][c] = '.'
keys.clear()
def bfs(): # bfs 탐색
global answer
queue = deque([(0, 0)])
visited = [[0] * (w + 2) for _ in range(h + 2)]
visited[0][0] = 1
while queue:
r, c = queue.popleft()
for idx in range(4):
nr = r + d[idx][0]
nc = c + d[idx][1]
if 0 <= nr < h+2 and 0 <= nc < w+2 and not visited[nr][nc]:
if maps[nr][nc] == '*':
continue
if ord('A') <= ord(maps[nr][nc]) <= ord('Z'):
continue
if maps[nr][nc] == '$':
answer += 1
if ord('a') <= ord(maps[nr][nc]) <= ord('z'):
keys.append(maps[nr][nc])
queue.append((nr, nc))
maps[nr][nc] = '.'
visited[nr][nc] = 1
for _ in range(int(input())):
h, w = map(int, input().split())
maps = [['.'] * (w+2)]
for _ in range(h):
row = sys.stdin.readline().rstrip()
row = '.' + row + '.'
maps.append(list(''.join(row)))
maps.append(['.'] * (w+2))
keys = deque(list(''.join(sys.stdin.readline().rstrip())))
answer = 0
while keys: # 열쇠로 문을 열고 BFS 탐색을 하기 때문에 열쇠가 존재할 때까지 반복한다.
if keys[0] == '0': keys.clear() # 열쇠가 주어지지 않았다면(0) keys를 비운다.
if keys: # 문을 열 수 있는 열쇠가 존재하면 unlock 함수 실행
unlock()
bfs()
print(answer)시간초과 해결에 많은 고민을 하였는데 visited를 매번 초기화하는 것이 오히려 효율적이었나보다... 🤔
