[백준] 구슬 탈출 2

문제 바로가기

from typing import List, Set, Dict, Tuple, Optional
from collections import deque


class Solution:
    def __init__(self, n: int, m: int, board: List[List[str]]):
        self.n = n
        self.m = m
        self.board = board

    def exit_beads_2(self):
        red = blue = None
        # 빨강, 파랑 구슬 위치 특정 및 board에서 지우기
        for r in range(1, self.n - 1):
            for c in range(1, self.m - 1):
                if self.board[r][c] == "R":
                    red = (r, c)
                    self.board[r][c] = "."
                if self.board[r][c] == "B":
                    blue = (r, c)
                    self.board[r][c] = "."

        visited = set()
        visited.add((red, blue))
        count = 0
        q = deque()
        q.append((red, blue))
        # BFS
        while q and count < 10:
            same_depth = len(q)
            count += 1
            for i in range(same_depth):
                red, blue = q.popleft()
                for direction in range(4): # 위쪽부터 시계 방향
                    new_red, red_exit, new_blue, blue_exit = \
                    	self.tilt(red, blue, direction)
                    if blue_exit:
                        continue
                    if red_exit:
                        return count
                    tup = (tuple(new_red), tuple(new_blue))
                    if tup not in visited:
                        visited.add(tup)
                        q.append(tup)
        return -1

    def tilt(self, red, blue, dir):
        if dir == 0:  # up
            new_red, red_exit = self.move_up(*red)
            new_blue, blue_exit = self.move_up(*blue)
            if new_red == new_blue:
                if red[0] < blue[0]:
                    new_blue[0] += 1
                else:
                    new_red[0] += 1
        elif dir == 1:  # right
            new_red, red_exit = self.move_right(*red)
            new_blue, blue_exit = self.move_right(*blue)
            if new_red == new_blue:
                if red[1] > blue[1]:
                    new_blue[1] -= 1
                else:
                    new_red[1] -= 1
        elif dir == 2:  # down
            new_red, red_exit = self.move_down(*red)
            new_blue, blue_exit = self.move_down(*blue)
            if new_red == new_blue:
                if red[0] > blue[0]:
                    new_blue[0] -= 1
                else:
                    new_red[0] -= 1
        else:  # left
            new_red, red_exit = self.move_left(*red)
            new_blue, blue_exit = self.move_left(*blue)
            if new_red == new_blue:
                if red[1] < blue[1]:
                    new_blue[1] += 1
                else:
                    new_red[1] += 1
        return new_red, red_exit, new_blue, blue_exit

    def move_up(self, row: int, col: int, up: bool = True):
        met_exit = False
        range_obj = range(row - 1, 0, -1) if up else range(row + 1, self.n - 1)
        next_row = 1 if up else self.n - 2
        for i in range_obj:
            if self.board[i][col] != ".":
                if self.board[i][col] == "O":
                    met_exit = True
                next_row = i + (1 if up else -1)
                break
        return [next_row, col], met_exit

    def move_down(self, row: int, col: int):
        return self.move_up(row, col, up=False)

    def move_left(self, row: int, col: int, left: bool = True):
        met_exit = False
        range_obj = range(col - 1, 0, -1) if left else range(col + 1, self.m - 1)
        next_col = 1 if left else self.m - 2
        for i in range_obj:
            if self.board[row][i] != ".":
                if self.board[row][i] == "O":
                    met_exit = True
                next_col = i + (1 if left else -1)
                break
        return [row, next_col], met_exit

    def move_right(self, row: int, col: int):
        return self.move_left(row, col, left=False)


if __name__ == "__main__":
    n, m = map(int, input().split())
    board = list()
    for i in range(n):
        board.append(list(input()))

    solution = Solution(n, m, board)
    print(solution.exit_beads_2())