문제 링크: 9328 열쇠
문제 관찰:
문제 예제를 살펴보자.
1
5 17
.............$*
BAPCXY.X.
yxap$*
cz
. 는 다닐 수 있는 길
입력 받은 값을 . 로 감싸주면 별다른 처리 없이
BFS(0, 0)으로 해결 가능 하다.
아니면 매우 복잡은 처리가 필요하다.
BFS탐색 하면서
갈수 있는 문을 확인 해주고 가지고 있는 키로 갈수 있는 지 없는 지 판단 하고 처리해준다.
또한 키를 가졌을 때는 이때까지 방문 했지만 열지 못한 문이 있는 지 없는 지 확인 한후 처리 해준다.
import sys; input = lambda: sys.stdin.readline().rstrip()
from collections import deque
def BFS(x, y):
global ans
queue = deque()
queue.append((x,y))
visited[x][y] = 1
while queue:
x, y = queue.popleft()
for dx, dy in di:
nx, ny = dx + x, dy + y
# 벽체크
if nx < 0 or ny < 0 or nx > N + 1 or ny > M + 1: continue
# 방문 체크 & 못가는 곳 (*) 체크
if visited[nx][ny] or mapping[nx][ny] == '*': continue
# $ 발견
if mapping[nx][ny] == '$':
# visited[nx][ny] = 1
ans += 1
queue.append((nx, ny))
# 문 이면 door 에 넣어 준다.
elif mapping[nx][ny].isupper():
# 문에 해당 하는 키가 있으면
if key[ord(mapping[nx][ny])-65]:
queue.append((nx, ny))
# 문에 해당 하는 키가 없으면 door에 넣어준다.
else:
door[ord(mapping[nx][ny])-65].append((nx, ny))
# 열쇠도 넣어준다.
elif mapping[nx][ny].islower():
key[ord(mapping[nx][ny])-97] = 1
queue.append((nx, ny))
# 키를 가지고 있는 데 이미 방문해본 문이 있으면 텔레포트
if door[ord(mapping[nx][ny])-97] != 0:
while door[ord(mapping[nx][ny])-97]:
x, y = door[ord(mapping[nx][ny])-97].pop()
queue.append((x, y))
# 갈 수 있으면 가자~
elif mapping[nx][ny] == '.':
# visited[nx][ny] = 1
queue.append((nx, ny))
visited[nx][ny] = 1
T = int(input())
for _ in range(T):
N, M = map(int, input().split())
mapping = [['.'] * (M+2)] + [list('.' + input() + '.') for _ in range(N)] + [['.']*(M+2)]
firstkey = input()
key = [0] * 26 # 키는 소문자로 이루어져있다.
if firstkey == '0':
pass
else:
for k in firstkey:
key[ord(k)-97] = 1
door = [[] for _ in range(26)] # 문은 대문자, 이중 리스트로 구현
visited = [[0]*(M+2) for _ in range(N+2)]
di = [(0,1),(0,-1),(1,0),(-1,0)]
ans = 0
BFS(0, 0)
print(ans)
이 문제를 통해 얻은 것.
꽤나 긴 시간을 고민하고 푼 문제이다. (새벽 4시 까지 풀었다..)
자존감++
구현력++
즐거움++
다만,
구현력에서 여전히 아쉬움을 느끼고
문제 관찰에 대해 고민 해봐야겠다.