백준 16197 파이썬 - 두 동전

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

16197번: 두 동전

문제

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

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

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

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

코드

import sys
from collections import deque
n, m = map(int, sys.stdin.readline().split())
board = []
temp = []
for i in range(n):
    board.append(list(sys.stdin.readline().rstrip()))
    for j in range(m):
        if board[i][j] == "o":
            temp.append((i, j))
q = deque()
q.append((temp[0][0], temp[0][1], temp[1][0], temp[1][1], 0))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs():
    while q:
        x1, y1, x2, y2, count = q.popleft()
        if count >= 10:
            return -1
        for i in range(4):
            mx1 = x1 + dx[i]
            my1 = y1 + dy[i]
            mx2 = x2 + dx[i]
            my2 = y2 + dy[i]
            if 0 <= mx1 < n and 0 <= my1 < m and 0 <= mx2 < n and 0 <= my2 < m:
                if board[mx1][my1] == "#":
                    mx1, my1 = x1, y1
                if board[mx2][my2] == "#":
                    mx2, my2 = x2, y2
                q.append((mx1, my1, mx2, my2, count + 1))
            elif 0 <= mx1 < n and 0 <= my1 < m:
                return count + 1
            elif 0 <= mx2 < n and 0 <= my2 < m:
                return count + 1
    return -1
print(bfs())

풀이

입력 받은 값 중 동전이 있는 곳만 q에 넣고 dx와 dy를 더해주며 움직인다. 벽을 만나면 움직이지 않고, 한번에 count를 1씩 증가시키며 하나만 떨어졌을 경우 count + 1을 리턴해 출력한다. 모두 탐색해도 elif문에 들어가지 않는 경우 -1을 출력한다.