본문 바로가기
알고리즘/[python] 백준 BOJ

[python] 백준 9328 열쇠

by Alan_Kim 2023. 6. 22.
728x90
반응형

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

 

9328번: 열쇠

상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가

www.acmicpc.net

 

문제 해결

  • 주어진 열쇠를 찾고 열쇠에 맞는 문을 열어 최대한 많은 문서를 찾는 문제
  • 움직임을 보면 bfs를 이용하는 것이 편할 것 같다.
  • 하지만 갔던 길을 또 갈 수 있으므로 갔던 길을 체크하는 visited를 성과가 있을 때마다 리셋을 시켜줘야한다.
  • key의 유무를 dictionary를 통해 저장하면 좋을 것 같다.
  • 한 번 얻은 문서는 다시 중복해서 먹을 수 없으므로 문서를 얻었으면 answer += 1을 하고 '$'(문서 있음을 나타냄)를 '.' (빈공간)으로 바꿔준다.
  • 입구가 불규칙하게 정해져있으므로 구하기 귀찮으므로 각 행의 양 사이드에 '.'(빈공간)을 붙여 넓혀주고 출발지점을 (0,0)으로 고정시키면 더 편하게 코드를 짤 수 있다.

 

CODE

from collections import deque
def bfs():
    global answer
    que = deque()
    que.append((0,0))
    visited = [[0 for _ in range(w+2)] for _ in range(h+2)]
    visited[0][0] = 1
    dxs = [-1, 0, 0, 1]
    dys = [0, -1, 1, 0]
    while que:
        x, y = que.popleft()
        for dx, dy in zip(dxs,dys):
            nx = x + dx
            ny = y + dy
            if 0<=nx<h+2 and 0<=ny<w+2 and board[nx][ny] != '*' and visited[nx][ny] ==0:
                if 'A'<=board[nx][ny] <='Z':
                    if board[nx][ny].lower() not in key: continue
                elif 'a' <= board[nx][ny] <= 'z':
                    if board[nx][ny] not in key:
                        key[board[nx][ny]] = True
                        visited = [[0 for _ in range(w+2)] for _ in range(h+2)]
                elif board[nx][ny] == '$':
                    answer += 1
                    board[nx][ny] = '.'
                visited[nx][ny] = 1
                que.append((nx,ny))

if __name__=='__main__':
    t = int(input())
    for _ in range(t):
        h, w = map(int,input().split())
        board = [list(map(str,'.'+input()+'.')) for _ in range(h)]
        board = [['.']*(w+2)]+board+[['.']*(w+2)]
        key = dict()
        for i in input():
            if i.isalpha():
                key[i] = True
        answer = 0
        bfs()
        print(answer)

 

728x90
반응형

댓글