문제

N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, 두 동전의 위치는 다르다.

버튼은 "왼쪽", "오른쪽", "위", "아래"와 같이 4가지가 있다. 버튼을 누르면 두 동전이 버튼에 쓰여 있는 방향으로 동시에 이동하게 된다.

• 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.
• 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.
• 그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다.이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.

두 동전 중 하나만 보드에서 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

# 16197
import sys
input = lambda: sys.stdin.readline().strip()

from collections import deque

# 1. 큐에 동전1, 동전2 를 넣어 bfs 진행
# 2. 동전 한개만 보드판에서 떨어진 경우의 시간 계산

n, m = map(int, input().split())
arr = [list(map(str, input())) for _ in range(n)]

coin = []
for x in range(n):
    for y in range(m):
        if arr[x][y] == "o":
            coin.append((x, y))

dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1]


def check_out(x, y):
    global n, m
    if x < 1 or y < 1 or x > n or y > m:
        return True
    return False


def bfs():
    global n, m, coin
    queue = deque()
    x1, y1 = coin[0]
    x2, y2 = coin[1]
    visited = [[[[-1] * (m+2) for _ in range(n+2)] for _ in range(m+2)] for _ in range(n+2)]
    visited[x1+1][y1+1][x2+1][y2+1] = 0
    
    queue.append((x1+1, y1+1, x2+1, y2+1))
    min_time = 11
    
    while queue:
        x1, y1, x2, y2 = queue.popleft()
        
        if check_out(x1, y1) != check_out(x2, y2):
            min_time = min(min_time, visited[x1][y1][x2][y2])
            continue
            
        if check_out(x1, y1) or check_out(x2, y2):
            continue
            
        for i in range(4):
            nx1, ny1 = x1 + dx[i], y1 + dy[i]
            nx2, ny2 = x2 + dx[i], y2 + dy[i]
            
            if check_out(nx1, ny1) == False and arr[nx1-1][ny1-1] == "#":
                nx1, ny1 = x1, y1
            if check_out(nx2, ny2) == False and arr[nx2-1][ny2-1] == "#":
                nx2, ny2 = x2, y2
                
            if visited[nx1][ny1][nx2][ny2] == -1 or visited[x1][y1][x2][y2] + 1 < visited[nx1][ny1][nx2][ny2]:
                visited[nx1][ny1][nx2][ny2] = visited[x1][y1][x2][y2] + 1
                queue.append((nx1, ny1, nx2, ny2))
                
    return min_time
                
    
time = bfs()
if time > 10:
    print("-1")
else:
    print(time)

백준 16197 두 동전