백준 13460 : 구슬 탈출 2

https://www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

 

해결 방법 : BFS

• 10번까지 판을 기울이는 모든 경우를 탐색한다.
  • 중복 탐색을 허용한다면 최악의 경우 $4^10$ 만큼을 탐색하게 되므로, visited 해쉬테이블을 만들어 구슬의 위치가 이전의 어떤 시점과 동일하다면 더 이상 탐색하지 못하도록 한다.  
• 한 번의 탐색 마다 빨간 구슬과 파란 구슬을 상하좌우로 벽에 부딪힐 때까지 움직이며, 움직이는 과정에 빨간 구슬만 구멍에 들어갔다면 현재 count 를 반환한다.
• 빨간 구슬과 파란 구슬이 겹쳐지는 경우를 방지하기 위한 방법으로 조건문을 두었다.

import sys
input = sys.stdin.readline
from collections import deque

def solution(N, M, board):
    D = [(0,1), (1,0), (0,-1), (-1,0)] # 상하좌우 이동 가중치
    for r in range(N): # 최초 빨간 구슬, 파란 구슬 위치 찾기
        for c in range(M):
            if board[r][c] == 'R':
                redRow, redCol = r, c
            if board[r][c] == 'B':
                blueRow, blueCol = r, c
        
    Q = deque([(redRow, redCol, blueRow, blueCol, 0)])
    visited = dict() # 중복 탐색 방지
    visited[(redRow, redCol, blueRow, blueCol)] = True
    while Q:
        RR, RC, BR, BC, count = Q.popleft()
        if count == 10: return -1 # 종료 조건

        for d in D: # 상하좌우 기울이기
            redGoal = blueGoal = False # 각 구슬이 구멍에 들어갔는지를 나타내는 변수
            nRR, nRC, nBR, nBC = RR, RC, BR, BC
            while board[nRR + d[0]][nRC + d[1]] != '#': # 벽에 부딪힐 때까지 
                nRR += d[0]
                nRC += d[1]
                if board[nRR][nRC] == 'O': # 구멍에 들어감
                    redGoal = True
            while board[nBR + d[0]][nBC + d[1]] != '#':
                nBR += d[0]
                nBC += d[1]
                if board[nBR][nBC] == 'O':
                    blueGoal = True

            if redGoal and not blueGoal: # 빨간 구슬만 구멍에 들어간 경우
                return count + 1
            if blueGoal: # 파란 구슬이 구멍에 들어간 경우 현재 탐색은 무효
                continue

            if nRR == nBR and nRC == nBC: # 빨간 구슬과 파란 구슬이 겹쳐진 경우, 
                if RR == BR and RC < BC:
                    if d[1] == 1: nRC -= 1
                    else: nBC += 1
                elif RR == BR and RC > BC:
                    if d[1] == 1: nBC -= 1
                    else: nRC += 1
                elif RC == BC and RR < BR:
                    if d[0] == 1: nRR -= 1
                    else: nBR += 1
                else:
                    if d[0] == 1: nBR -= 1
                    else: nRR += 1
            
            if visited.get((nRR, nRC, nBR, nBC)) is None: # 탐색하지 않은 구슬 위치일 경우,
                visited[(nRR, nRC, nBR, nBC)] = True
                Q.append((nRR, nRC, nBR, nBC, count + 1)) # 탐색 Q에 push
                
    return -1


if __name__ == '__main__':
    N, M = map(int, input().split())
    board = [input() for _ in range(N)]
    result = solution(N, M, board)
    print(result)