두 동전

문제

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

버튼은 왼쪽/오른쪽/위/아래와 같이 4가지가 있습니다.
버튼을 누르면 두 동전은 동시에 버튼에 쓰여져있는 방향으로 이동합니다.

• 동전이 이동하려는 칸이 벽이면 동전은 이동하지 않습니다.
• 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어집니다.
• 그 이외의 경우에는 이동하려는 방향으로 한칸 이동합니다. (동전이 곂쳐도 됩니다.)

한 동전만을 보드에서 떨어뜨리기 위해 최소한으로 버튼을 몇번 눌러야하는지를 구하는 문제입니다.

제약조건

• 세로 N, 가로 M 일때 1 <= N,M <= 20
• 버튼을 10번 보다 많이 누르는 경우 -1을 반환합니다.

풀이

BFS 알고리즘을 이용했습니다. queue에는 최소한으로 이동했을때, 이동가능한 두 동전의 발견된 위치들을 저장합니다.
queue의 크기 단위로 버튼 누르는 횟수를 셉니다.

다음과 같은 경우 queue에 집어넣지 않습니다.

• 두 동전이 동시에 떨어짐. -> 더 이상 이동가능하지 않습니다. 따라서 queue의 정의에 따라 queue에 넣을수없습니다.
• 두 동전이 이동하지 않음 / 두 동전이 이미 발견됨. -> 해당 경우는 이동가능하지만 문제에서 최소한의 버튼을 누르는것을 요구하기 때문에 답이 무조건 될수없으므로 queue에 넣지 않습니다.
• 두 동전중 하나만 떨어짐. -> 답을 발견했으므로 더 이상 진행할 필요가 없습니다.
  위의 경우를 제외한 경우는 queue에 집어넣습니다.

queue의 크기가 0이 되거나 버튼 누른횟수가 10을 넘어갈경우, -1을 반환합니다.

코드

'''
Created by jun on 21/05/25
'''
import collections

buttons = [(0, -1), (0, 1), (-1, 0), (1, 0)] #y, x

N, M = map(int, input().split())
board = [list(input()) for _ in range(N)]
coins = list()

for y in range(N):
    for x in range(M):
        if board[y][x] == 'o':
            coins.append((y, x))
# ((3, 0), (4, 0))
def bfs(coins):
    discovered = set()
    discovered.add(coins)
    queue = collections.deque()
    queue.append(coins)
    
    cnt = 0
    while queue and cnt < 10:
        cnt += 1
        for _ in range(len(queue)):
            coin1, coin2 = queue.popleft()
            for button in buttons:
                dropped_coin = 0

                #새로운 동전의 위치
                new_coin1 = (coin1[0] + button[0], coin1[1] + button[1])
                new_coin2 = (coin2[0] + button[0], coin2[1] + button[1])

                #동전 위치 조정
                #동전 1이 떨어진 경우 / 범위를 벗어난 경우.
                if not(0 <= new_coin1[0] < N and 0 <= new_coin1[1] < M):
                    dropped_coin += 1

                #동전 1이 #인경우
                #버튼 조작을 취소한다.
                elif board[new_coin1[0]][new_coin1[1]] == '#':
                    new_coin1 = (coin1[0], coin1[1])

                #동전 2가 떨어진경우
                if not(0 <= new_coin2[0] < N and 0 <= new_coin2[1] < M):
                    dropped_coin += 1

                # 동전 2이 #인경우
                # 버튼 조작을 취소한다.
                elif board[new_coin2[0]][new_coin2[1]] == '#':
                    new_coin2 = (coin2[0], coin2[1])

                # 예외처리 : 이미 방문한 경우 / 안 움직인 경우
                # 모든 조작이 완료된 상태
                if (new_coin1, new_coin2) in discovered:
                    continue

                #하나도 안떨어진 경우 -> 재평가
                if dropped_coin == 0:
                    queue.append((new_coin1, new_coin2))
                    discovered.add((new_coin1, new_coin2))

                #하나만 떨어진경우 -> 정답
                elif dropped_coin == 1:
                    return cnt
                #둘다 떨어진경우 -> 평가 종료.
    return -1
print(bfs(tuple(coins)))

새로 알게된 사실

판에서 동전을 이동시키는 법
move 함수를 선언해서 이동한 y,x를 반환하면 깔끔하게 짤수있다. (이동 불가할땐 -1 반환)