백준_9328_열쇠

문제

www.acmicpc.net/problem/9328

9328번: 열쇠

풀이

설계도를 입력 받을 때 테두리를 빈 칸 . 으로 채운다.

stack에 다음으로 탐색할 노드의 행과 열을 입력한다. [(r1, c1), (r2, c2)...]

더 이상 탐색할 노드가 없을 때까지(stack이 비어 있을 때까지) 탐색한다.

 

1) .를 만났을 때 상하좌우의 유효한 노드를 stack에 추가한다. 

    유효한 노드: 설계도 안에 존재하며 벽(*)이 아닌 노드

    중복을 체크하기 위해 해당 노드에 벽(*)을 세운다.

 

2) $를 만났을 때 (1)문서의 개수를 1만큼 늘린다. 상하좌우의 유효한 (2)노드를 stack에 추가한다. 

    유효한 노드: 설계도 안에 존재하며 벽(*)이 아닌 노드

    중복을 체크하기 위해 해당 노드에 벽(*)을 세운다.

 

3) 열쇠(소문자)를 만났을 때

    (1) 상근이가 가지고 있는 열쇠에 추가한다.

    (2) 상하좌우의 유효한 노드를 stack에 추가한다.

    (3) 열쇠로 열수 있는 문을 stack에 추가한다. 열지 못하는 문의 정보를 삭제한다.

        유효한 노드: 설계도 안에 존재하며 벽(*)이 아닌 노드

        중복을 체크하기 위해 해당 노드에 벽(*)을 세운다.

 

4) 문(대문자)을 만났을 때 

    4-1) 문을 열 수 있다면 상하좌우의 유효한 노드를 stack에 추가한다.

        유효한 노드: 설계도 안에 존재하며 벽(*)이 아닌 노드

        중복을 체크하기 위해 해당 노드에 벽(*)을 세운다.

 

    4-2) 문을 열 수 없다면 노드의 위치를 저장한다.

 

다음과 같은 예제가 주어질때 아래와 같이 동작한다.

# https://www.acmicpc.net/problem/9328 의 예제를 변형
1
5 17
*****************
.............**$*
*B*A*P*C**X*Y*.X.
*y*x*a*p**$*$**$*
*****************
cz

 

코드

from sys import stdin
from collections import defaultdict

N = int(stdin.readline())
for _ in range(N):
    # 설계도를 입력 받을 때 테두리를 빈 칸 . 으로 채우기
    h, w = map(int, stdin.readline().split())
    h_arr, w_arr = h + 2, w + 2
    arr = [["." for j in range(w_arr)] for i in range(h_arr)]
    for i in range(h) :
        arr[i+1][1:-2] = stdin.readline().strip()

    # 상근이가 이미 가지고 있는 열쇠
    keys = list(stdin.readline().strip())
    keys.append(".")

    stack = [(0, 0)] # 탐색할 노드를 저장
    ans = 0  # 상근이가 훔친 문서의 수
    unlock = defaultdict(list) # 열리지 않은 문을 저장 {필요한 키:[(r1, c1), (r2, c2)...]}

    while stack:
        r, c = stack.pop()
        candidate = [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]  # 좌우 상하 4개의 절점을 탐색 가능
        item = arr[r][c]

        if item == "$": ans += 1  # 문서를 얻습니다.

        elif item.lower() in keys: pass  # 문을 열 수 있습니다.

        elif item.islower():
            keys.append(item)  # 키를 얻습니다.
            candidate += unlock[item]  # 탐색 범위에 추가
            unlock[item] = list()  # 초기화

        elif item != "*":  # 문을 열지 못합니다.
            unlock[item.lower()].append((r, c))  # 필요한 키를 저장합니다.
            continue

        else: continue

        arr[r][c] = "*"  # 지나갈 수 없음

        for r1, c1 in candidate:
            if 0 <= r1 < h_arr and 0 <= c1 < w_arr:
                if arr[r1][c1] != "*":
                    stack.append((r1, c1))
    print(ans)