2 minute read

16197번 : 두 동전

문제 링크

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

문제 설명

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

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

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

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

입력

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

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

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

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

출력

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

문제풀이

아래 경우들을 신경쓰면서 bfs로 구현하면 쉽게 할 수 있다.

  1. bfs를 이용하여 큐에서 꺼낼 때 횟수가 10번 초과이면 -1을 출력
  2. 방문 여부 확인은 하지 않는다. 동전 하나를 위치 이동을 못하는 벽 방향으로 ‘일부러’ 이동시킬 수도 있기 때문이다.
from collections import deque
import sys
input = sys.stdin.readline

def move_coins(coin1, coin2) :
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]

    deq = deque([[coin1, coin2, 0]])   

    while deq : 
        coin1, coin2, cnt = deq.popleft()
        c1_y, c1_x = coin1
        c2_y, c2_x = coin2

        # 버튼 누른 횟수가 10번 초과면 -1 출력
        if cnt > 10 :
            return -1
            
        for i in range(4) : 
            coinInBoard = [False, False]
            c1_ny, c1_nx = c1_y+dy[i], c1_x+dx[i]
            c2_ny, c2_nx = c2_y+dy[i], c2_x+dx[i]

            # 첫 번째 동전이 보드 안에 들어오는 지 확인
            if 0 <= c1_ny < N and 0 <= c1_nx < M  :
                coinInBoard[0] = True

                # 만약 이동하는 곳이 벽이면 이동을 못하므로 이동 전 위치로 저장
                if board[c1_ny][c1_nx] == '#' :
                    c1_ny, c1_nx = c1_y, c1_x

            # 두 번째 동전이 보드 안에 들어오는 지 확인
            if 0 <= c2_ny < N and 0 <= c2_nx < M :
                coinInBoard[1] = True

                # 만약 이동하는 곳이 벽이면 이동을 못하므로 이동 전 위치로 저장
                if board[c2_ny][c2_nx] == '#' :
                    c2_ny, c2_nx = c2_y, c2_x

            # 보드 안에 있는 동전이 2개이고, 두 동전 중 하나라도 기존 위치에서 이동했으면 큐에 넣기
            if sum(coinInBoard) == 2 and [c1_ny, c1_nx, c2_ny, c2_nx] != [c1_y, c1_x, c2_y, c2_x] : 
                deq.append([[c1_ny, c1_nx], [c2_ny, c2_nx], cnt+1])

            # 보드 안에 있는 동전이 1개이고, 버튼 누른 총합이 10번 이하이면 횟수 출력 아니면 -1 출력
            elif sum(coinInBoard) == 1 :
                if cnt < 10 :
                    return cnt+1
                else :
                    return -1
    return -1
    
N, M = map(int, input().split())
board = [input() for _ in range(N)]
coin1, coin2 = -1, -1

# 두 동전 위치 찾기
for i in range(N) :
    for j in range(M) :
        if board[i][j] == 'o' and coin1 == -1:
            coin1 = [i, j]
        elif board[i][j] == 'o' and coin1 != -1:
            coin2 = [i, j]

print(move_coins(coin1, coin2))

Comments

You May Also Enjoy