백준 13460

• 문제 : https://acmicpc.net/problem/13460
• 아이디어 : 최소 이동 횟수를 찾는 문제이므로, BFS 알고리즘 사용

알고리즘

1. 장난감을 상하좌우로 움직이는 네 가지 경우에 대해 적용되는 이동 함수 move 구현

• 이때 이동 방향에 따라 먼저 움직이는 구슬과 나중에 움직이는 구슬을 각각 first, second 로 변수 정의하여 작동하도록 설정

2. BFS 알고리즘 구현

• 방문 여부를 나타내는 array를 정의해야 하는데, 이때 중요한 것은 구슬이 움직이면서 한 구슬이 재방문하지 않는다면 나머지 구슬은 재방문이 가능함. 따라서 두 구슬이 모두 재방문하는 경우만 제외하면 되므로, 두 구슬의 모든 좌표를 포함하는 array, 즉 4차원 배열을 구성해야 함!

3. 결과 출력

• red 구슬과 구슬구멍의 좌표 hole이 대응하는 이동횟수들 중 최솟값을 사용하는데, 이때 10이 넘어가는 경우나 전체 횟수가 0인 경우(구슬이 빠져나오지 못한 경우)를 제외하고 출력.

전체 코드

# 구슬 탈출 2 > BFS problem

import sys
from collections import deque
from copy import deepcopy
N, M = map(int,sys.stdin.readline().split())
array = [sys.stdin.readline().strip() for _ in range(N)]

for i in range(N):
    if 'R' in array[i]:
        red = [array[i].index('R'),i]
        array[i] = array[i].replace("R",".")
    if 'B' in array[i]:
        blue = [array[i].index('B'),i]
        array[i] = array[i].replace("B",".")
    if 'O' in array[i]:
        hole = [array[i].index('O'),i]

coord = {'r':red, 'b':blue}

# 이동하는 함수 정의
def move(coordinates, d, i):
    coord = deepcopy(coordinates) # 본래 좌표 훼손 방지
    # d(direction) : 가로 0, 세로 1 / i(increasing) : 증가 1, 감소 -1
    if (coord['r'][d] - coord['b'][d])*i >= 0:
        first, second = 'r', 'b'
    else:
        first, second = 'b', 'r'

    while True: # first 구슬
        coord[first][d] += i
        if coord[first] == hole: # 구멍에 빠짐
            break
        elif array[coord[first][1]][coord[first][0]] == "#": # 벽에 부딪힘
            coord[first][d] -= i
            break

    while True: # second 구슬
        coord[second][d] += i
        if coord[second] == hole:
            break
        elif coord[second] == coord[first] and coord[second] != hole:
            coord[second][d] -= i
            break
        elif array[coord[second][1]][coord[second][0]] == "#":
            coord[second][d] -= i
            break
    
    return coord

# BFS Algorithm
deq = deque({})
deq.append(coord)
array_cnt = [[[[0]*N for _ in range(M)] for __ in range(N)] for ___ in range(M)] # 두 구슬 위치 count
array_cnt[coord['r'][0]][coord['r'][1]][coord['b'][0]][coord['b'][1]] = 1

while deq:
    coord = deq.popleft()
    xr, yr = coord['r']
    xb, yb = coord['b']
    moved = []
    
    for d,i in [[0,1],[0,-1],[1,1],[1,-1]]:
        move_coord = move(coord,d,i)
        moved.append(deepcopy(move_coord))

    for m in moved:
        nxr, nyr = m['r']
        nxb, nyb = m['b']
        if (m['b'] != hole) and (array_cnt[nxr][nyr][nxb][nyb] == 0): # 파란공 빠진경우 제외
            if (m['r'] == hole):
                array_cnt[nxr][nyr][nxb][nyb] = array_cnt[xr][yr][xb][yb] + 1
            else:
                array_cnt[nxr][nyr][nxb][nyb] = array_cnt[xr][yr][xb][yb] + 1
                deq.append(m)

ls = sum(array_cnt[hole[0]][hole[1]], [])
ls_cnt = [i for i in ls if i>0] # 0이 아닌 원소들만

if ls_cnt:
    if min(ls_cnt) > 11:
        print(-1)
    else:
        print(min(ls_cnt)-1)
else:
    print(-1)