문제

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

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

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

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

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

입력

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

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

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

출력

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

풀이

접근방법

시간제한이 2초, 메모리가 512MB,
N과 M의 크기가 20보다 같거나 작으므로 시간과 메모리가 충분하다.
( 최대 depth가 10으로 제한)
그래서 단순 BFS를 통해서 시뮬레이션을 해본다.

또한 구현 방법은 두 가지가 떠오른다.
1. 각 동전을 관리하는 큐를 각각 선언
2. 하나의 큐에서 두 개의 동전을 모두 관리.

하나의 큐에서 2개의 동전을 모두 관리하는 방향으로 진행.
보드의 외곽선에 한 칸씩 여유를 두고, 동전이 이동했을때.

• 움직임 가능 여부.
• 움직였다면 보드 밖으로 떨어졌는지?
  - 동전이 2개가 떨어졌는가?
  • 동전이 하나만 떨어졌는가?

를 확인하면서 진행

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {
	// static StringBuilder sb;
	static int N, M;
	static char[][] map;

	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};

	final static char COIN = 'o';
	final static char BLANK = '.';
	final static char WALL = '#';

	static class Point {
		int x;
		int y;

		Point(int a, int b) {
			x = a;
			y = b;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		// sb = new StringBuilder();
		String[] splitedLine = in.readLine().split(" ");
		N = stoi(splitedLine[0]);
		M = stoi(splitedLine[1]);

		map = new char[N + 2][M + 2];
		for (int i = 0; i <= N + 1; ++i) {
			for (int j = 0; j <= M + 1; ++j) {
				map[i][j] = BLANK;
			}
		}
		Queue<Point> q = new ArrayDeque<>();
		for (int i = 1; i <= N; ++i) {
			String line = in.readLine();
			for (int j = 1; j <= M; ++j) {
				map[i][j] = line.charAt(j - 1);
				if (map[i][j] == COIN)
					q.add(new Point(i, j));
			}
		}

		int depth = 1;
		while (!q.isEmpty()) {
			if (depth > 10)
				break;

			int size = q.size() / 2;
			while (size-- > 0) {
				Point first = q.poll(); // 첫번째 코인
				Point second = q.poll(); // 두번째 코인

				for (int d = 0; d < 4; ++d) {
					Point firstCoinNext = getNextPosition(first, d);
					Point secondCoinNext = getNextPosition(second, d);

					boolean resultFirst = isInBoard(firstCoinNext.x, firstCoinNext.y);
					boolean resultSecond = isInBoard(secondCoinNext.x, secondCoinNext.y);
					if (resultFirst == true && resultSecond == true) {
						// 동전 2개가 모두 보드 안쪽에 위치하는 경우
						q.add(firstCoinNext);
						q.add(secondCoinNext);
					} else if ((resultFirst == true && resultSecond == false)
						|| (resultFirst == false && resultSecond == true)) {
						// 동전 2개 중 1개가 보드 밖으로 나간 경우
						System.out.println(depth);
						return;
					} else {
						// 동전 2개가 모두 떨어진 경우
						// do nothing
					}
				}
			}
			depth++;
		}
		System.out.println(-1);
	}

	private static Point getNextPosition(Point p, int d) {
		int nextX = p.x + dx[d];
		int nextY = p.y + dy[d];
		if (map[nextX][nextY] != WALL && isInRange(nextX, nextY))
			return new Point(nextX, nextY);
		else
			return new Point(p.x, p.y);
	}

	private static boolean isInRange(int x, int y) {
		if (0 <= x && x <= N + 1 && 0 <= y && y <= M + 1)
			return true;
		return false;
	}

	private static boolean isInBoard(int x, int y) {
		if (1 <= x && x <= N && 1 <= y && y <= M)
			return true;
		return false;
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}

}