24. SW_Test 연습 백준 16197번 두 동전

문제

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

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

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

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

입력

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

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

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

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

출력

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

 

#pragma warning (disable : 4996)
#include <iostream>
#include <cstdio>
#include<queue>
#include<cstring>
#include <vector>
using namespace std;
int N, M;
int dir[4][2] = { {-1,0} ,{1,0} ,{0,-1}, {0,1} };
int ans = 999999;
char Map[20][20];
struct coin{
	int y, x;
	bool life = true;
};
vector <coin> coins;
void Movecoin(int num, int d) {
	int cunY = coins[num].y;
	int cunX = coins[num].x;;
	int nextY = cunY + dir[d-1][0];
	int nextX = cunX + dir[d-1][1];
	if (Map[nextY][nextX] == '#') {
		return;
	}
	Map[cunY][cunX] = '.';
	if (Map[nextY][nextX] =='o' ) {
		coins[num].y = nextY;
		coins[num].x = nextX;
		return;
	}
	if (nextY < 0 || nextY >= N || nextX < 0 || nextX >= M) {
		coins[num].life = false;
		return;
	}
	// .
	Map[nextY][nextX] = 'o';
	coins[num].y = nextY;
	coins[num].x = nextX;
}
void sol(int cnt, int d) {
	if (cnt>ans) {
		return;
	}
	if ((coins[0].life == false && coins[1].life == true) || (coins[0].life == true && coins[1].life == false)) {
		return;
	}
	if ((coins[0].life == false && coins[1].life == false)) {
		return;
	}
	if (cnt == 11) {
		return;
	}
	else {
		char tmpMap[20][20];
		int oney = coins[0].y;
		int onex = coins[0].x;
		int twoy = coins[1].y;
		int twox = coins[1].x;
		bool lifeone = coins[0].life;
		bool lifetwo = coins[1].life;
		memcpy(tmpMap, Map, sizeof(tmpMap));
		if ( d==1) {
			if (coins[0].y < coins[1].y) {
				Movecoin(0, 1);
				Movecoin(1, 1);
			}
			else {
				Movecoin(1, 1);
				Movecoin(0, 1);
			}
		}
		else if (d == 2) {
			if (coins[0].y > coins[1].y) {
				Movecoin(0, 2);
				Movecoin(1, 2);
			}
			else {
				Movecoin(1, 2);
				Movecoin(0, 2);
			}
		}
		else if (d==3) {
			if (coins[0].x < coins[1].x) {
				Movecoin(0, 3);
				Movecoin(1, 3);
			}
			else {
				Movecoin(1, 3);
				Movecoin(0, 3);
			}
		}
		else if (d == 4) {
			if (coins[0].x > coins[1].x) {
				Movecoin(0, 4);
				Movecoin(1, 4);
			}
			else {
				Movecoin(1, 4);
				Movecoin(0, 4);
			}
		}
		if ((coins[0].life==false && coins[1].life ==true) || (coins[0].life == true && coins[1].life == false)) {
			ans = min(ans, cnt);
		}
		sol(cnt +1, 1);
		sol(cnt +1, 2);
		sol(cnt +1, 3);
		sol(cnt +1, 4);
		coins[0].y= oney;
		coins[0].x= onex;
		coins[1].y= twoy;
		coins[1].x= twox;
		coins[0].life= lifeone;
		coins[1].life= lifetwo;
		memcpy(Map, tmpMap, sizeof(Map));
	}
}
int main() {
	freopen("input.txt", "r", stdin);
	cin >> N >> M;
	for (int i = 0; i < N;i++) {
		for (int j = 0; j < M; j++) {
			cin >> Map[i][j];
			if (Map[i][j]== 'o') {
				coin c;
				c.y = i;
				c.x = j;
				coins.push_back(c);
			}
		}
	}
	sol(0, 0);
	if (ans ==999999) {
		cout << -1;
	}
	else {
		cout << ans;
	}
	return 0;
}