Baekjoon 9328. 열쇠 / Python

9328.열쇠

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. '.'은 이동가능한 곳
2. '*'은 이동 불가능한 곳
3. '$'는 문서가 있는 곳
4. '소문자 알파벳'은 열쇠
5. '대문자 알파벳'은 잠긴 문
6. 건물 밖에서 안으로 돌아다닐 수 있으며, 문서를 가장 많이 챙길 수 있을 때, 문서의 개수를 구하는 문제

2. 해결 방식

1. 기본적인 bfs문제에다 문/열쇠의 개념이 추가되었다.
2. 우선 빌딩 을 '.'안에 넣는 방식으로 건물 외부에 대한 배열을 추가했다.
3. 새로운 열쇠를 얻을 때 마다, 방문했던 잠긴 문을 열 수 있는 가능성이 생기므로 이를 해결해주는 것이 중요하다.
4. 새로운 열쇠를 얻게 되면, 방문했던 잠긴 문들 중에 얻은 열쇠로 열리는 문이 있다면 큐에 추가하는 방식으로 해결했다.

3. 정답 코드

import sys
# sys.stdin = open("C:/Users/ghtjd/Desktop/tmp/python/input.txt", "r")

input = sys.stdin.readline
from collections import deque as dq

# 입력받기 : 빌딩주변을 다 '.'(이동가능) 으로 채워놓는다.
def input_data():
    h, w = map(int, input().split())
    buildings = [['.'] * (w + 2) for _ in range(h + 2)]

    for i in range(1, h + 1):
        building = input()
        buildings[i][1:-1] = building

    key_had = list(input())
    if '0' in key_had:key_had = []
    return h, w, buildings, key_had

direction = [
    (-1, 0),  # 상
    (1, 0),   # 하
    (0, -1),  # 좌
    (0, 1)    # 우
]
def sol(h, w, buildings, key_had):
    closed_door = []
    paper_get = 0
    visit = []
    q = dq()
    q.append((0, 0))
    visit.append(0)
    while q:
        x, y = q.popleft()
        for dx, dy in direction:
            nx, ny = x + dx, y + dy
            if nx in range(h + 2) and ny in range(w + 2):
                # 이미 방문한 경우
                if (nx * (w + 2) + ny) in visit:continue
                visit.append(nx * (w + 2) + ny)
                char = buildings[nx][ny]
                # 벽인 경우
                if char == '*':continue
                # 문인데 키 없는 경우
                if char.isupper() and char.lower() not in key_had:
                    closed_door.append((nx, ny, char))
                    continue
                # 문서인 경우
                if char == '$':
                    paper_get += 1
                    buildings[nx][ny] = '.'
                # 열쇠인 경우
                if char.islower():
                    if char in key_had: # 이미 있는 키
                        buildings[nx][ny] = '.'
                    else:	# 새로운 키
                        key_had.append(char)
                        buildings[nx][ny] = '.'
                        # 새로운 키로 이미 방문한 문 중에 열 수 있다면 열고 q에 추가
                        for cx, cy, alphabet in closed_door:
                            if alphabet.lower() == char:
                                buildings[cx][cy] = '.'
                                q.append((cx, cy))
                # 문이고 키 있는 경우
                if char.isupper():
                    if char.lower() in key_had:
                        buildings[nx][ny] = '.'
                q.append((nx, ny))
                
    print(paper_get)
    return

T = int(input())

for _ in range(T):
    h, w, buildings, key_had = input_data() # 문의 높이, 너비, 건물의 배열, 가지고 있는 키
    sol(h, w, buildings, key_had)