[백준] 16197번 - 두 동전

📩 출처

문제

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

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

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

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

입력

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

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

• o: 동전
• .: 빈 칸
• #: 벽
  동전의 개수는 항상 2개이다.

출력

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

👉 생각

• 인덱스 에러 신경쓰지 않기 위해 입력받는 이차원 배열을 0으로 감싸준다.
• 동전 2개의 위치를 파악해서 너비우선탐색을 하는 함수 bfs의 인자로 삽입한다.
• bfs를 돌릴 때 조건은 다음과 같다.
  1. 첫번째 if문에서 동전이 하나라도 떨어지는 경우가 있다면, 둘 다 떨어지는 경우를 제외하고 각각 한 동전씩 떨어질 때마다 -1 혹은 현재 cnt를 반환한다. 여기서 cnt는 움직일때마다 1씩 추가해준 값이다.
  2. 어떤 동전도 떨어지지 않았다면, 3가지 조건이 필요하다. (1) 두 동전 모두 다음 경로가 벽, (2) 1번 동전의 다음 경로가 벽이거나, (3) 2번 동전의 다음 경로가 벽일 때를 나누어서 벽인 경우 이전 위치를 q에 담아준다.
  3. 동전 1개가 떨어지고 그 때의 cnt가 10 이하인 경우를 제외하고는 -1을 리턴해준다.

from collections import deque

def bfs(coin1, coin2):
    x, y = coin1; xx, yy = coin2
    q = deque([])
    q.append((x, y, xx, yy, 0))
    while q:
        x, y, xx, yy, cnt = q.popleft()
        if cnt > 10:
            return -1

        if arr[x][y] == 0 or arr[xx][yy] == 0:
            if arr[x][y] == 0 and arr[xx][yy] == 0:
                pass
            else:
                return cnt

        for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
            nx, ny, nxx, nyy = x + dx, y + dy, xx + dx, yy + dy
            # 동전이 하나라도 떨어지는 경우
            if arr[nx][ny] == 0 or arr[nxx][nyy] == 0:
                if arr[nx][ny] == 0 and arr[nxx][nyy] != 0:
                    if cnt < 10:
                        return cnt + 1
                    else:
                        return -1
                elif arr[nx][ny] != 0 and arr[nxx][nyy] == 0:
                    if cnt < 10:
                        return cnt + 1
                    else:
                        return -1
            else:
                if arr[nx][ny] != '#' and arr[nxx][nyy] != '#':
                    q.append((nx, ny, nxx, nyy, cnt+1))
                elif arr[nx][ny] != '#' and arr[nxx][nyy] == '#':
                    q.append((nx, ny, xx, yy, cnt+1))
                elif arr[nx][ny] == '#' and arr[nxx][nyy] != '#':
                    q.append((x, y, nxx, nyy, cnt+1))
    return -1
n, m = map(int, input().split())
arr = [[0] * (m+2)] + [[0] + list(input()) + [0] for _ in range(n)] + [[0] * (m+2)]
coin = []
for i in range(n+1):
    for j in range(m+1):
        if arr[i][j] == 'o':
            coin.append([i, j])
    if len(coin) == 2:
        break
coin1, coin2 = coin
print(bfs(coin1, coin2))