16197 두 동전

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

16197번: 두 동전

두 동전 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

512 MB

2116

892

583

42.555%

문제

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

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

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

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

입력

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

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

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

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

출력

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

 

 

<풀이>

1. 문제의 조건

 (1)10칸을 넘게 눌러야 한다면 return -1;

 

 (2)동전이 이동할 조건,

 

 (3)동전이 이동하지 못하였을때,

 

 (4)동전이 떨어 졌을때

   4-(1) (하나만 떨어졌을때, 두개 다 떨어졌을때)

 

문제의 조건을 아우르게 할 수 있는 부분을 고려하여 재귀 함수를 만드는데

매개변수로 무엇을 넘겨주는가의 현재와 다음 상태의 값을 결정하는 부분이 중요하다.

 

2. 답을 찾는 경우

  (1) (동전이 하나만 떨어진 경우,  return 움직인 횟수)

 

 

3.움직인 횟수의 최솟값을 출력,

 

 

4. 동전은 언제나 두 개 이므로 동전의 좌표를 각각 (x,y) , (x2,y2) 로 처리.

 

#include<iostream>
#include<vector>
using namespace std;

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

char arr[20][20];
int check[20][20];
int check2[20][20];
int N, M;

vector<pair<int, int>> v;
int go(int index, int x, int y, int x2, int y2);
int main(void)
{
	cin >> N >> M;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			cin >> arr[i][j];
			if (arr[i][j] == 'o')
			{
				v.push_back(make_pair(i, j));
				arr[i][j] = '.';
			}
		}
	}
	int x, y, x2, y2;
	x = v[0].first; y = v[0].second;
	x2 = v[1].first; y2 = v[1].second;

	
	cout << go(0, x, y, x2, y2) << '\n';
	return 0;
}

int go(int index, int x, int y, int x2, int y2)
{
	if (index == 11)
		return -1;

	bool fall1 = false, fall2 = false;

	//동전1 떨어진 경우
	if (x < 0 || x >= N || y < 0 || y >= M) 
		fall1 = true;
	//동전2 떨어진 경우
	if (x2 < 0 || x2 >= N || y2 < 0 || y2 >= M) 
		fall2 = true;

	//둘 다 떨어진 경우
	if (fall1 && fall2) 
		return -1;

	if (fall1 || fall2)
		return index;

	int ans = -1;
	for (int i = 0; i < 4; ++i)
	{
		int xn = x + dx[i]; int yn = y + dy[i];
		int x2n = x2 + dx[i]; int y2n = y2 + dy[i];

		//이동 못하는경우;
		if (xn >= 0 && xn < N && yn >= 0 && yn < M && arr[xn][yn] == '#')
		{
			xn = x;
			yn = y;
		}
		if (x2n >= 0 && x2n < N && y2n >= 0 && y2n < M && arr[x2n][y2n] == '#')
		{
			x2n = x2;
			y2n = y2;
		}

		int temp = go(index + 1, xn, yn, x2n, y2n);
		
		if (temp == -1) 
			continue;
		if (ans > temp || ans == -1)
		{
			ans = temp;
		}
	}
	return ans;
	
}