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
반응형
'알고리즘 > [python] 백준 BOJ' 카테고리의 다른 글
[python] 백준 2283 구간 자르기 (0) | 2023.06.26 |
---|---|
[python] 백준 20057 마법사 상어와 토네이도 (0) | 2023.06.23 |
[python] 백준 1208 부분수열의 합 (0) | 2023.06.22 |
[python] 백준 20055 컨베이어 벨트 위의 로봇 (0) | 2023.06.22 |
[python] 백준 11758 CCW (0) | 2023.06.14 |
댓글