[Baekjoon] 16197번 : 두 동전

1. 문제

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

• BFS 문제

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

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

동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.
동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.
그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다.
이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.
두 동전 중 하나만 보드에서 떨어뜨리기 위해 
버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

// 입력
첫째 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 20)
둘째 줄부터 N개의 줄에는 보드의 상태가 주어진다.

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

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

// 예제 입력 1 
1 2
oo

// 예제 출력 1 
1

// 예제 입력 2 
6 2
.#
.#
.#
o#
o#
##

// 예제 출력 2 
4

// 예제 입력 3 
6 2
..
..
..
o#
o#
##

// 예제 출력 3 
3

// 예제 입력 4 
5 3
###
.o.
###
.o.
###

// 예제 출력 4 
-1

// 예제 입력 5 
5 3
###
.o.
#.#
.o.
###

// 예제 출력 5 
3

2. 핵심 아이디어

3. Python 문제풀이

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

n, m = map(int, input().split())
arr = []
money = deque()
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

for i in range(n) :
  arr.append(list(input().rstrip()))
  for j in range(m) :
    if arr[i][j] == 'o' :
      money.append((i, j))
      arr[i][j] = '.'

visited = set()
visited.add(''.join(map(str, money)))

def bfs() :
  q = deque()
  q.append((0, money))
  while q :
    cnt, now = q.popleft()
    if cnt >= 10 :
      return -1
    for k in range(4) :
      tmp = copy.deepcopy(now)
      for _ in range(2) :
        x, y = tmp.popleft()
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= nx < n and 0 <= ny < m :
          if arr[nx][ny] == '.' :
            tmp.append((nx, ny))
          elif arr[nx][ny] == '#' :
            tmp.append((x, y))
      if len(tmp) == 1 :
        return cnt + 1
      elif not tmp :
        continue
      visit = ''.join(map(str, tmp))
      if visit not in visited :
        visited.add(visit)
        q.append((cnt+1, tmp))
  return -1


print(bfs())

4. Java 문제풀이