백준 9328 열쇠 python

청천·2022년 11월 11일
0

백준

목록 보기
37/41

문제 링크: 9328 열쇠
문제 관찰:

문제 예제를 살펴보자.
1
5 17


.............$*
BAPC
XY.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시 까지 풀었다..)
자존감++
구현력++
즐거움++

다만,
구현력에서 여전히 아쉬움을 느끼고
문제 관찰에 대해 고민 해봐야겠다.

0개의 댓글