문제 링크
https://www.acmicpc.net/problem/9328
접근
문제가 딱히 어렵진 않다.
다만, 고려해야될 예외 상황들을 잘 생각해야한다.
(최근 다시 푼 문제였는데, 가장자리에 문과 열쇠가 있는 경우를 기존 풀이에선 고려하지 않아 재채점 결과 오답이 되었다.)
풀이
우선순위 큐를 이용하여 문자(.*$aA)별로 우선순위를 다르게하여 중요한 곳을 먼저 탐색하도록 하였다.
def priority(c):
if c == "$": # goal
return 0
if "a" <= c <= "z": # key
return 1
if c == ".": # space
return 3
if "A" <= c <= "Z": # door
if c.lower() in keys: # 열 수 있는 문
return 2
else: # 못 여는 문
return 4주의깊게 봐야할 부분은 문이다.
문은 열 수 있는 문과 열 수 없는 문으로 나뉘는데, 열 수 없는 문은 열쇠가 생기기 전까지 방문조차 하지 않도록 코드를 작성하였다.
h, w = map(int, input().split())
board = [list(input()) for _ in range(h)]
keys = set(input())
found_locked_door = {} # 잠겨있는 문이 있는 위치들
for alp in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
found_locked_door.setdefault(alp, set()) # 특정 알파벳의 문이 둘 이상일수도 있어서 문 위치를 set에 저장
visit = [[0 for _ in range(w)] for _ in range(h)]
pq = PriorityQueue()다음은 주요 변수들이다.
keys 는 말 그대로 가지고있는 열쇠들의 알파벳을 set으로 저장하는 것이다.
found_locked_door 잠겨있는 문의 위치를 저장하는 딕셔너리이다.
found_locked_door ["A"] = {(1,5), (5,7), (20,5), ...} 이런 식으로 여태까지 발견했던 문A의 위치들을 저장한다.
for i in range(h):
for j in range(w):
# 가장자리만 탐색
if (i == 0 or i == h - 1 or j == 0 or j == w - 1) and board[i][j] != "*":
p = priority(board[i][j])
if p == 4: # 못 여는 문
found_locked_door[board[i][j]].add((i, j))
continue
pq.put((p, i, j))
visit[i][j] = 1"상근이는 처음에는 빌딩의 밖에 있으며, 빌딩 가장자리의 벽이 아닌 곳을 통해 빌딩 안팎을 드나들 수 있다."고 하므로 맨 처음에는 가장자리만 체크한다.
들어갈 수 있는 곳은 우선순위 큐에 넣어 우선순위별로 먼저 방문한다.
예를 들어 가장자리에 $도 있고 열쇠 x도 있고 빈공간 .도 있다고 치면, $이 있는 곳에 먼저 방문하고, 그 다음에 열쇠 x를 먹고, 그 다음에 빈공간에 방문하는 식으로 말이다.
추가적으로 못 여는 문은 아직 큐에 넣지 말고, 문의 위치만 기록한다.
while not pq.empty():
p, y, x = pq.get()
if p == 0: # goal
ans += 1
elif p == 1: # key
keys.add(board[y][x])
if board[y][x].upper() in found_locked_door: # 해당 열쇠에 맞는 문 찾았었음, 열어버리자!
for door_y, door_x in found_locked_door[board[y][x].upper()]:
# 해당 열쇠에 맞는, 이미 찾았었던, 모든 문에 대해
visit[door_y][door_x] = 1
pq.put((2, door_y, door_x))
elif p == 2 or p == 3:
pass
for i in range(4):
ny, nx = y + dy[i], x + dx[i]
if in_range(ny, nx) and not visit[ny][nx] and board[ny][nx] != "*":
np = priority(board[ny][nx])
if np == 4: # 못 여는 문
found_locked_door[board[ny][nx]].add((ny, nx))
continue
visit[ny][nx] = 1
pq.put((np, ny, nx))마지막으로 메인 알고리즘이다.
윗부분(조건문 부분)과 아랫부분(반복문,탐색 부분)으로 나누어 설명하자면,
일단 윗부분은 현재 방문한 위치에서 수행할 동작에 대한 것이다.
p==0으로 $, 우리가 훔쳐야하는 물건이면 ans를 1 증가하는 식으로 말이다.
현재 위치가 빈공간(.)이거나 열린 문이면 특별히 뭘 할 필요가 없으므로 pass.
(못 여는 문은 큐에 들어갈 수 없으므로 조건 조차 없다.)
중요한 부분은, 현재 위치에 열쇠가 있는 경우이다.
일단 기본적으로 열쇠를 발견하면 keys에 추가한다.
그리고 현재 열쇠에 맞는 문을 방문한 적이 있었다면, 탐색했었는 "그 문"들을 모두 열어준다.
열린 문들은 이제 방문할 수 있으므로 큐에 넣는다. (열린문의 우선순위인 2를 가지고 간다.)
아랫부분은... 그냥 상하좌우 탐색이다.
아까와 같이 못 여는 문은 아직 방문하지 않고 문의 위치만 기록한다.
정답 코드
import sys
from queue import PriorityQueue
# sys.setrecursionlimit(10 ** 8) # pypy 제출시 삭제!
input = lambda: sys.stdin.readline().rstrip()
in_range = lambda y, x: 0 <= y < h and 0 <= x < w
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]
def priority(c):
if c == "$": # goal
return 0
if "a" <= c <= "z": # key
return 1
if c == ".": # space
return 3
if "A" <= c <= "Z": # door
if c.lower() in keys: # 열 수 있는 문
return 2
else: # 못 여는 문
return 4
for _ in range(int(input())):
h, w = map(int, input().split())
board = [list(input()) for _ in range(h)]
keys = set(input())
found_locked_door = {} # 잠겨있는 문이 있는 위치들
for alp in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
found_locked_door.setdefault(alp, set()) # 특정 알파벳의 문이 둘 이상일수도 있어서 문 위치를 set에 저장
visit = [[0 for _ in range(w)] for _ in range(h)]
pq = PriorityQueue()
ans = 0
for i in range(h):
for j in range(w):
# 가장자리만 탐색
if (i == 0 or i == h - 1 or j == 0 or j == w - 1) and board[i][j] != "*":
p = priority(board[i][j])
if p == 4: # 못 여는 문
found_locked_door[board[i][j]].add((i, j))
continue
pq.put((p, i, j))
visit[i][j] = 1
while not pq.empty():
p, y, x = pq.get()
if p == 0: # goal
ans += 1
elif p == 1: # key
keys.add(board[y][x])
if board[y][x].upper() in found_locked_door: # 해당 열쇠에 맞는 문 찾았었음, 열어버리자!
for door_y, door_x in found_locked_door[board[y][x].upper()]:
# 해당 열쇠에 맞는, 이미 찾았었던, 모든 문에 대해
visit[door_y][door_x] = 1
pq.put((2, door_y, door_x))
elif p == 2 or p == 3:
pass
for i in range(4):
ny, nx = y + dy[i], x + dx[i]
if in_range(ny, nx) and not visit[ny][nx] and board[ny][nx] != "*":
np = priority(board[ny][nx])
if np == 4: # 못 여는 문
found_locked_door[board[ny][nx]].add((ny, nx))
continue
visit[ny][nx] = 1
pq.put((np, ny, nx))
print(ans)