[백준] 9328. 열쇠 (Python)

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

9328번: 열쇠

 

📌 주의할 점

- 상근이는 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있는데, 문제에서 주어지는 빌딩을 .으로 감싸 들어갈 입구를 마련해주었다.

- 열쇠를 주웠으면 이제껏 가지 못했던 곳을 갈 수 있으므로 (문을 열어서) visit배열을 초기화해준다.

 

🖥️ Pypy3 통과

import sys
from collections import deque

input = sys.stdin.readline
dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def BFS():
    global doc
    q = deque()
    q.append((0, 0))
    visit = [[0]*(X+2) for _ in range(Y+2)]
    visit[0][0] = 1
    while q:
        ny, nx = q.popleft()
        for i, j in dir:
            dy, dx = ny+i, nx+j
            if 0 <= dy < Y+2 and 0 <= dx < X+2:
                if visit[dy][dx] == 1: continue
                if board[dy][dx] == '.':
                    visit[dy][dx] = 1
                    q.append((dy, dx))
                elif board[dy][dx] == '$': # 문서이면
                    board[dy][dx] = '.'
                    visit[dy][dx] = 1
                    doc += 1 # 주움
                    q.append((dy, dx))
                elif board[dy][dx].islower(): # 키 발견 시
                    door[ord(board[dy][dx])-ord('a')] = 1 # 문 리스트에 표시
                    visit = [[0]*(X+2) for _ in range(Y+2)] # visit 배열 초기화
                    board[dy][dx] = '.'
                    q.append((dy, dx))
                elif board[dy][dx].isupper(): # 방이면
                    if door[ord(board[dy][dx])-ord('A')]: # 열쇠 있으면
                        board[dy][dx] = '.'
                        visit[dy][dx] = 1
                        q.append((dy, dx))
                else:
                    continue

T = int(input())

for tc in range(T):
    Y, X = map(int, input().split())
    board = [[] for _ in range(Y+2)]
    board[0] = board[Y+1] = ['.']*(X+2)
    door = [0]*26
    doc = 0 # 훔친 문서 갯수
    for idx in range(1, Y+1): # 새로운 맵
        temp_lst = list(input())
        temp_lst.pop() # sys => 처리
        board[idx] = ['.'] + temp_lst + ['.']
    temp = list(input())
    temp.pop() # sys => 처리
    for k in temp:
        if k != '0':
            door[ord(k)-ord('a')] = 1 # 문에 열쇠 있다고 표시
    for y in range(Y+2):
        for x in range(X+2):
            if ord(board[y][x]) >= ord('A') and ord(board[y][x]) <= ord('Z'): # 방이면
                if door[ord(board[y][x])-ord('A')]: # 보유 중인 열쇠로 열리면 열기
                    board[y][x] = '.'
    BFS()
    print(doc)

- 답은 맞았으나, Python3로는 시간초과가 나는 게 신경쓰였다.

- Python3로도 통과하게 할 순 없을까?🤔 고민하며 여러 시도 및 구글링한 결과, 현재 코드에서는 BFS 내에서 visit 배열만 초기화해준 뒤 계속 다시 돌리고 있기 때문임을 알게 되었다.

 

📌 방법 1 (Python 3 통과) : q 초기화

- 위의 코드에서 열쇠를 주워서 visit을 초기화할 때 q도 함께 초기화해준다.

import sys
from collections import deque

input = sys.stdin.readline
dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def BFS():
    global doc
    q = deque()
    q.append((0, 0))
    visit = [[0]*(X+2) for _ in range(Y+2)]
    visit[0][0] = 1
    while q:
        ny, nx = q.popleft()
        for i, j in dir:
            dy, dx = ny+i, nx+j
            if 0 <= dy < Y+2 and 0 <= dx < X+2:
                if visit[dy][dx] == 1: continue
                if board[dy][dx] == '.':
                    visit[dy][dx] = 1
                    q.append((dy, dx))
                elif board[dy][dx] == '$': # 문서이면
                    board[dy][dx] = '.'
                    visit[dy][dx] = 1
                    doc += 1 # 주움
                    q.append((dy, dx))
                elif board[dy][dx].islower(): # 키 발견 시
                    door[ord(board[dy][dx])-ord('a')] = 1 # 문 리스트에 표시
                    visit = [[0]*(X+2) for _ in range(Y+2)] # visit 배열 초기화
                    q.clear()
                    board[dy][dx] = '.'
                    q.append((dy, dx))
                elif board[dy][dx].isupper(): # 방이면
                    if door[ord(board[dy][dx])-ord('A')]: # 열쇠 있으면
                        board[dy][dx] = '.'
                        visit[dy][dx] = 1
                        q.append((dy, dx))
                else:
                    continue

T = int(input())

for tc in range(T):
    Y, X = map(int, input().split())
    board = [[] for _ in range(Y+2)]
    board[0] = board[Y+1] = ['.']*(X+2)
    door = [0]*26
    doc = 0 # 훔친 문서 갯수
    for idx in range(1, Y+1): # 새로운 맵
        temp_lst = list(input())
        temp_lst.pop() # sys => 처리
        board[idx] = ['.'] + temp_lst + ['.']
    temp = list(input())
    temp.pop() # sys => 처리
    for k in temp:
        if k != '0':
            door[ord(k)-ord('a')] = 1 # 문에 열쇠 있다고 표시
    for y in range(Y+2):
        for x in range(X+2):
            if ord(board[y][x]) >= ord('A') and ord(board[y][x]) <= ord('Z'): # 방이면
                if door[ord(board[y][x])-ord('A')]: # 보유 중인 열쇠로 열리면 열기
                    board[y][x] = '.'
    BFS()
    print(doc)

 

📌 방법 2 (Python 3 통과) : BFS 종료

- 위의 코드와 달리 열쇠를 주웠을 때 visit을 초기화하거나 하지 않고, door 리스트에 주웠음을 표시해준다.

- 키를 모두 사용할 때까지 BFS를 계속 돌려준다.

import sys
from collections import deque

input = sys.stdin.readline
dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def unlock():
    global door
    if sum(door):
        for y in range(Y+2):
            for x in range(X+2):
                if board[y][x].isupper():
                    if door[ord(board[y][x])-ord('A')]:
                        board[y][x] = '.'
        door = [0]*26
def BFS():
    global doc
    q = deque()
    q.append((0, 0))
    visit = [[0]*(X+2) for _ in range(Y+2)]
    visit[0][0] = 1
    while q:
        ny, nx = q.popleft()
        for i, j in dir:
            dy, dx = ny+i, nx+j
            if 0 <= dy < Y+2 and 0 <= dx < X+2:
                if visit[dy][dx] == 1: continue
                if board[dy][dx] == '*': continue
                elif board[dy][dx].isupper():continue
                elif board[dy][dx] == '$': # 문서면 줍기
                    doc += 1
                elif board[dy][dx].islower(): # 키 발견 시
                    door[ord(board[dy][dx])-ord('a')] = 1 # 문 리스트에 표시
                board[dy][dx] = '.'
                visit[dy][dx] = 1
                q.append((dy, dx))

T = int(input())

for tc in range(T):
    Y, X = map(int, input().split())
    board = [[] for _ in range(Y+2)]
    board[0] = board[Y+1] = ['.']*(X+2)
    door = [0]*26
    doc = 0 # 훔친 문서 갯수
    for idx in range(1, Y+1): # 새로운 맵
        temp_lst = list(input())
        temp_lst.pop() # sys => 처리
        board[idx] = ['.'] + temp_lst + ['.']
    temp = list(input())
    temp.pop() # sys => 처리
    for k in temp:
        if k != '0':
            door[ord(k)-ord('a')] = 1 # 문에 열쇠 있다고 표시
    for y in range(Y+2):
        for x in range(X+2):
            if ord(board[y][x]) >= ord('A') and ord(board[y][x]) <= ord('Z'): # 방이면
                if door[ord(board[y][x])-ord('A')]: # 보유 중인 열쇠로 열리면 열기
                    board[y][x] = '.'
    while True:
        unlock()
        BFS()
        if sum(door) == 0:
            break
    print(doc)

 

✏️ 방법 1(1272ms)보다는 방법 2(920ms)가 시간이 더 적게 걸렸고, 메모리는 동일하게 32580kb 사용!