백준 16197 c++ 두 동전

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

16197번: 두 동전

문제

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

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

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

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

입력

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

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

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

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

출력

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

---

#include <iostream>
using namespace std;

int n, m;
char arr[21][21];
int dx[] = { 1,-1,0,0 };//상하좌우
int dy[] = { 0,0,-1,1 };

int nx[2];//현재 코인의 위치
int ny[2];

int minimum = 11;
bool check;

//인자 count, 1번동전 위치, 2번동전 위치
void dfs(int count, int nx1, int ny1,int nx2,int ny2)
{
	if (count == 10)
	{
		return;
	}

	for (int i = 0; i < 4; i++)
	{
		int nextX1 = nx1+dx[i];
		int nextY1 = ny1+dy[i];
		int nextX2 = nx2+dx[i];
		int nextY2 = ny2+dy[i];

		if ((nextX1 < 0 || nextX1 >= n || nextY1 < 0 || nextY1 >= m) && (nextX2 < 0 || nextX2 >= n || nextY2 < 0 || nextY2 >= m))//2개다 범위 밖으로 나갔을 때
		{
			continue;
		}
		else if ((nextX1 >= 0 && nextX1 < n && nextY1 >= 0 && nextY1 < m) && (nextX2 >= 0 && nextX2 < n && nextY2 >= 0 && nextY2 < m))//2개다 범위 안일때
		{
			if (arr[nextX1][nextY1] == '#' && arr[nextX2][nextY2] == '#')
				continue;
			if (arr[nextX1][nextY1] == '#')
			{
				nextX1 = nx1;
				nextY1 = ny1;
			}
			if (arr[nextX2][nextY2] == '#')
			{
				nextX2 = nx2;
				nextY2 = ny2;
			}
			dfs(count + 1, nextX1, nextY1, nextX2, nextY2);
		}
		else
		{
			minimum = min(minimum, count+1);
			return;
		}
	}
}

int main()
{
	//입력
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> arr[i][j];
		}
	}
	//코인 위치 저장
	int k = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (arr[i][j] == 'o')
			{
				nx[k] = i;
				ny[k] = j;//현재 코인의 위치 초기화
				k++;
			}
		}
	}
	
	dfs(0, nx[0], ny[0], nx[1], ny[1]);

	if (minimum == 11)
		cout << -1;
	else
		cout << minimum;

	return 0;
}