[13460] 구슬 탈출 2(골드 1)

13460번: 구슬 탈출 2

빨강, 파랑 구슬을 보드에서 중력으로 옮겨가면서 구멍으로 빨강 구슬만 빠질 때의 최소 횟수를 구하는 문제이다.

생각했던 주요 요소는 다음과 같다.

• 보드를 기울이면 막힌 곳까지 쭉 간다.
  • move 함수를 통해서 막힌 곳까지 이동시킨다.
• 보드를 기울였을 때 빨강, 파랑이 겹치지 않아야 한다.
  • 기울이는 방향에 따라서 먼저 있는 구슬을 먼저 이동시킨다.
• dfs or bfs를 활용할 수 있을 것 같다.
  • 처음에는 dfs를 활용 → 불필요한 연산이 많았다, 재귀 함수의 깊이가 깊어져서 오류 발생 가능성
  • bfs를 활용 → 해를 찾았을 때 바로 반복을 멈출 수 있었다.
• 10번을 넘기거나 기울여도 구슬이 안움직이면 멈춘다.
  • 10번을 넘기면 q에 추가하지 않도록 했다.
  • 구슬이 안움직이면 q에 추가하지 않도록 했다.

풀이 과정은 다음과 같다.

board 배열에 벽, 구멍을 기록한다. 구슬은 따로 좌표만 가지고 있는다. 이후에 구슬 좌표를 lean 함수로 넘겨서 왼쪽, 오른쪽, 위, 아래로 기울여본다(기울이는 함수는 move).

import sys
import collections

def move(dir, i, j, another):
  isOut = False
  originI, originJ = i, j
  if dir == 'left':
    while board[i][j - 1] != '#' and [i, j - 1] != another:
      j -= 1
      if board[i][j] == 'O':
        isOut = True
        i, j = 0, 0

        break
  elif dir == 'right':
    while board[i][j + 1] != '#' and [i, j + 1] != another:
      j += 1
      if board[i][j] == 'O':
        isOut = True
        i, j = 0, 0
        
        break
  elif dir == 'up':
    while board[i - 1][j] != '#' and [i - 1, j] != another:
      i -= 1
      if board[i][j] == 'O':
        isOut = True
        i, j = 0, 0
        
        break
  else:
    while board[i + 1][j] != '#' and [i + 1, j] != another:
      i += 1
      if board[i][j] == 'O':
        isOut = True
        i, j = 0, 0

        break
  isMove = abs(originI - i) + abs(originJ - j) > 0

  return [isMove, isOut, [i, j]]

def lean():
  global answer

  (dir, count, red, blue) = q.pop()
  redResult, blueResult = False, False
  redMove, blueMove = False, False
  if dir == 'left':
    if red[1] < blue[1]:
      [redMove, redResult, red] = move(dir, *red, blue)
      [blueMove, blueResult, blue] = move(dir, *blue, red)
    else:
      [blueMove, blueResult, blue] = move(dir, *blue, red)
      [redMove, redResult, red] = move(dir, *red, blue)
  elif dir == 'right':
    if red[1] > blue[1]:
      [redMove, redResult, red] = move(dir, *red, blue)
      [blueMove, blueResult, blue] = move(dir, *blue, red)
    else:
      [blueMove, blueResult, blue] = move(dir, *blue, red)
      [redMove, redResult, red] = move(dir, *red, blue)
  elif dir == 'up':
    if red[0] < blue[0]:
      [redMove, redResult, red] = move(dir, *red, blue)
      [blueMove, blueResult, blue] = move(dir, *blue, red)
    else:
      [blueMove, blueResult, blue] = move(dir, *blue, red)
      [redMove, redResult, red] = move(dir, *red, blue)
  else:
    if red[0] > blue[0]:
      [redMove, redResult, red] = move(dir, *red, blue)
      [blueMove, blueResult, blue] = move(dir, *blue, red)
    else:
      [blueMove, blueResult, blue] = move(dir, *blue, red)
      [redMove, redResult, red] = move(dir, *red, blue)
  if redResult and not blueResult:
    answer = min(answer, count + 1)

    return
  elif (redResult and blueResult) or (not redResult and blueResult):

    return
  elif (redMove or blueMove) and count + 1 < answer:
    for _dir in filter(lambda a: a != dir, dirs):
      q.appendleft((_dir, count + 1, red, blue))

n, m = map(int, sys.stdin.readline().strip().split(' '))
board = [[] for _ in range(n)]
red, blue = None, None
dirs = ['left', 'right', 'up', 'down']
for i in range(n):
    line = sys.stdin.readline().strip()
    for j, l in enumerate(line):
      if l == 'B':
        blue = [i, j]
        board[i].append('.')
      elif l == 'R':
        red = [i, j]
        board[i].append('.')
      else:
        board[i].append(l)
q = collections.deque([(dir, 0, red, blue) for dir in dirs])
answer = 11
while len(q) > 0:
  lean()

print(answer if answer < 11 else -1)