[Baekjoon] 두 동전

문제

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

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

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

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

입력

첫째 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 20)

둘째 줄부터 N개의 줄에는 보드의 상태가 주어진다.

• o: 동전
• .: 빈 칸
• #: 벽

동전의 개수는 항상 2개이다.

출력

첫째 줄에 두 동전 중 하나만 보드에서 떨어뜨리기 위해 눌러야 하는 버튼의 최소 횟수를 출력한다. 만약, 두 동전을 떨어뜨릴 수 없거나, 버튼을 10번보다 많이 눌러야 한다면, -1을 출력한다.

예제

Example 1:

Input: 
1 2
oo
Output: 
1

Example 2:

Input:
6 2
.#
.#
.#
o#
o#
##
Output:
4

Example 3:

Input:
6 2
..
..
..
o#
o#
##
Output:
3

Example 4:

Input:
5 3
###
.o.
###
.o.
###
Output:
-1

Example 5:

Input:
5 3
###
.o.
#.#
.o.
###
Output:
3

조건

시간 제한 : 2초

메모리 제한 : 512 MB

풀이과정

풀이 1

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

n, m = map(int, input().split())

graph = []
coins = []

for i in range(n):
    c = list(input())
    graph.append(c)
    for j in range(m):
        if c[j] == "o":
            coins.append((i, j))

q = deque()

q.append((coins,0))

ans = int(1e9)

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

while q:
    coin, level = q.popleft()

    if ans < level:
        break

    # 10번 이상이면 break
    if level > 10:
        ans = min(ans, level)
        break

    # 4가지 버튼에 따라서
    for k in range(4):
        down = 0
        ncoin = []

        x, y = coin[0]
        xx, yy = coin[1]

        nx = x + dx[k]
        ny = y + dy[k]
        nxx = xx + dx[k]
        nyy = yy + dy[k]

        # 몇개 떨어지는지 조사
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            down += 1
        if nxx < 0 or nxx >= n or nyy < 0 or nyy >= m:
            down += 1

        if down == 0:
            if graph[nx][ny] == "#":
                nx, ny = x, y
            if graph[nxx][nyy] == "#":
                nxx, nyy = xx, yy

            q.append(([(nx, ny), (nxx, nyy)], level+1))
        elif down == 1:
            ans = min(ans, level+1)

if ans == int(1e9) or ans > 10:
    print(-1)
else:
    print(ans)