문제 링크

문제 해결

맵에 있는 탐색 가능한 모든 문서의 갯수를 찾는 문제로, BFS를 이용하여 풀었다. 특이한 점은 주어진 열쇠로 맵에 있는 문을 열어서 이동할 수 가 있다는것인데, 열쇠를 맵을 탐색하면서 추가적으로 획득할 수 있기 때문에 이 부분을 유의하여 풀어야 한다.

입력

for _ in range(int(input())):
  height, width = map(int, input().split())
  floor = [list(input()) for _ in range(height)]
  keys = set(input())

  visited = [[0 for _ in row] for row in floor]
  documents = 0
  doors = {}  # 열리지 않은 문 리스트
  for door in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
    doors.setdefault(door, set())

2차원 맵을 입력받기위해 floor변수에 list comprehension을 이용하여 2중 리스트로 입력받았다.
중복 탐색을 방지하기 위해 floor와 같은 크기의 맵 변수visited와 열쇠가 생길 때 열쇠없이 지나간 문을 탐색하기 위한 key가 알파벳 대문자 문, value가 좌표를 담을 set()인 dictionary doors 변수를 초기화하였다.

탐색

탐색할 경로들 담는 paths의 리스트의 원소들이 없어질 때까지 반복문을 도는 구조로 기본적인 순회를 구현하였다.
현재 자리에서 상,하,좌,우로 움직여 각 위치에 맞는 문자를 확인한다.

  • 벽(*): 다음 자리 순회
  • 빈 공간(.): paths 리스트에 추가
  • 문서($): 찾은 문서 숫자를 카운팅 후, 빈 공간(.)으로 바꿔준 뒤, paths 리스트에 추가한다
  • 문(ABCD...Z): 열쇠가 있으면, floor를 빈 공간(.)으로 바꿔준 뒤, paths 리스트에 추가한다. 열쇠가 없다면 다음에 방문해야 할 문 변수 doors에 현재 좌표를 추가한다
  • 열쇠(abcd...z): 못 열었던 문들 중 일치하는 열쇠가 있다면 paths에 추가하여 탐색할 수 있도록 한다

코드

from enum import Enum

# move helper
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

class Space(Enum):
  EMPTY_SPACE = 1
  WALL = 2
  DOCUMENT = 3
  DOOR = 4
  KEY = 5

def checkRange(x: int, y: int):
  if x < 0 or x >= width or y < 0 or y >= height:
    return False
  return True

def checkSpace(what):
  if what == '.':
    return Space.EMPTY_SPACE
  elif what == '*':
    return Space.WALL
  elif what == '$':
    return Space.DOCUMENT
  elif 'A' <= what <= 'Z':
    return Space.DOOR
  elif 'a' <= what <= 'z':
    return Space.KEY

def solve(y: int, x: int):
  global documents
  global doors
  paths = []  # discovering paths (queue)

  what = floor[y][x]
  space = checkSpace(what)

  if space == Space.WALL:
    return
  elif space == Space.DOCUMENT:
    documents += 1
    floor[y][x] = '.'
  elif space == Space.DOOR:
    if what.lower() in keys:
      floor[y][x] = '.'
    else:
      doors[what].add((x,y))
      return
  elif space == Space.KEY:
    if what.upper() in doors:
      for x,y in doors[what.upper()]:
        paths.append({'x': x, 'y': y})
    keys.add(floor[y][x].lower())
    floor[y][x] = '.'

  paths.append({'x': x, 'y': y})

  while (len(paths)):
    cur = paths.pop()

    # 중복 탐색 방지
    if visited[cur['y']][cur['x']]:
      continue
    else:
      visited[cur['y']][cur['x']] = 1

    for idx in range(4):
      curX = cur['x'] + dx[idx]
      curY = cur['y'] + dy[idx]
      if not checkRange(curX, curY):
        continue

      # 현재 자리 체크
      what = floor[curY][curX]
      space = checkSpace(what)
      if space == Space.WALL:
        continue
      elif space == Space.DOCUMENT:
        documents += 1
        floor[curY][curX] = '.'
        paths.append({'x': curX, 'y': curY})
      elif space == Space.DOOR:
        # 현재 갖고있는 키중에 해당하는 키가 있는지 체크
        if what.lower() in keys:
          floor[curY][curX] = '.'
          visited[curY][curX] = 0
          paths.append({'x': curX, 'y': curY})
        # 키를 갖고있지 않으면 열리지 않은 문 리스트에 추가
        else:
          doors[what].add((curX,curY))
      elif space == Space.KEY:
        if what.upper() in doors:
          for x,y in doors[what.upper()]:
            paths.append({'x': x, 'y': y})
        keys.add(what)
        floor[curY][curX] = '.'
        visited[curY][curX] = 0
        paths.append({'x': curX, 'y': curY})
      elif space == Space.EMPTY_SPACE:
        paths.append({'x': curX, 'y': curY})

for _ in range(int(input())):
  height, width = map(int, input().split())
  floor = [list(input()) for _ in range(height)]
  keys = set(input())
  visited = [[0 for _ in row] for row in floor]
  documents = 0

  doors = {}  # 열리지 않은 문의 좌표를 담을 dictionary 변수
  for door in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
    doors.setdefault(door, set()) 

  for i in range(height):
    for j in range(width):
      # visit only edge of the map
      if (i == 0 or i == height - 1 or j == 0 or j == width - 1):
        solve(i, j)

  print(documents)