[Python] 백준 9328 열쇠

 

 

문제

상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다.

상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.

https://www.acmicpc.net/problem/9328

 

 

 

 

 

난이도

골드 1

 

 

 

코드

import sys
from collections import deque

def search() :
    global answer

    # BFS
    while queue :
        posX, posY = queue.popleft()

        tmp = graph[posX][posY]
        # print(tmp, posX, posY)
        go = True
        if tmp == '$' :
            answer += 1
        elif 'a' <= tmp <= 'z' :
            have_key[ord(tmp)-97] = True
        elif 'A' <= tmp <= 'Z' :
            if not have_key[ord(tmp)-ord('A')] :
                go = False
                door.append((tmp, posX, posY))
                visit[posX][posY] = False

        if go :
            for mx, my in move :
                new_x = posX + mx
                new_y = posY + my
                if 0 <= new_x < h and 0 <= new_y < w :
                    if not visit[new_x][new_y] and graph[new_x][new_y] != '*':
                        queue.append((new_x,new_y))
                        visit[new_x][new_y] = True

T = int(sys.stdin.readline())
move = [(-1,0),(1,0),(0,-1),(0,1)]
result = []
for _ in range(T) :
    h, w = map(int,sys.stdin.readline().split())
    graph = []
    have_key = [False] * 26 # 0~25 97~122
    visit = [[False for _ in range(w)] for _ in range(h)]
    answer = 0
    for _ in range(h) :
        x = list(sys.stdin.readline().rstrip())
        graph.append(x)
    key = list(sys.stdin.readline().rstrip())
    if key[0] != '0' :
        for k in key :
            have_key[ord(k)-97] = True
    
    # 초기화
    queue = deque()
    for i in range(h) :
        for j in range(w) :
            if i == 0 or i == (h-1) or j == 0 or j == (w-1) :
                if graph[i][j] != '*' :
                    queue.append((i,j))
                    visit[i][j] = True
    
    door = []

    while True :
        search()

        # 대문자 갈 수 있는 곳 추가
        gg = True
        for ddoor, go_x, go_y in door :
            if have_key[ord(ddoor) - ord('A')] and not visit[go_x][go_y]:
                queue.append((go_x, go_y))
                visit[go_x][go_y] = True
                gg = False

        # 없으면 종료
        if gg :
            break

    result.append(answer)

for r in result :
    print(r)

 

 

 

 

풀이

이번 코드는 좀 길다.

하지만 로직만 잘 세우면 시간초과가 난다거나 구현이 어렵지 않았다.

 

내가 세운 로직은

1. 처음에 건물 둘레에서 들어갈 수 있는 곳을 찾아서 큐에 넣는다. (= '*'이 아닌 경우를 찾는다.)
2. 큐에서 하나씩 꺼내 BFS 돌린다.
3. BFS에서는 
   
   1. '$'인 경우, answer += 1 하고 상하좌우 중 방문안했고 벽이 아닌 좌표를 큐에 넣는다.
   2. 소문자인 경우, 해당 키를 가지고 있다는 처리를 하고  상하좌우 중 가능한 좌표를 큐에 넣는다. (have_key[ord(tmp)-97] = True)
   3. 대문자인 경우, 해당 키를 소유하고 있으면 상하좌우 중 가능한 좌표를 큐에 넣는다.
      대문자인데 해당 키를 소유하고 있지 않은 경우 따로 리스트에 해당 대문자와 좌표를 저장해두고 방문처리를 취소한다.
   4. '.'인 경우, 상하좌우 중 가능한 좌표를 큐에 넣는다.
4. BFS가 종료되었으면 대문자와 좌표가 저장된 리스트에서 키를 얻어서 갈 수 있게 된 좌표들은 큐에 넣고 다시 BFS를 돌린다.
5. 더 이상 방문할 수 있는 곳이 없을 때 까지 반복한다.