[백준] 16197번 : 두 동전

www.acmicpc.net/problem/16197

16197번: 두 동전

---

<C++>

//c++

#include <bits/stdc++.h>
#define F_I ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
char arr[24][24];
int dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };

int n, m;
int isinside(int x, int y) //그 좌표가 arr안에 있는 좌표인지 확인
{
	if (x >= 0 && x < n && y >= 0 && y < m)
		return 1;
	return 0;
}

int go(int cnt, int x1, int y1, int x2, int y2)
{
	if (cnt == 11) //최소 횟수가 10회를 초과한다면 -1 반환
		return -1;
	bool f1 = false, f2 = false;
	if (isinside(x1, y1) == 0)
		f1 = true;
	if (isinside(x2, y2) == 0)
		f2 = true;
	if (f1 && f2)
		return -1; // 두 동전이 모두 보드 안에 있지 않다면, -1 반환
	if (f1 || f2)
		return cnt; // 두 동전 중 하나만 보드 밖으로 떨어졌다면, 그때의 cnt(버튼 누른 횟수) 반환
        
	int ans = -1;
	for (int i = 0; i < 4; i++)
	{
		int nx1 = x1 + dir[i][0];
		int ny1 = y1 + dir[i][1];
		int nx2 = x2 + dir[i][0];
		int ny2 = y2 + dir[i][1];
		if (isinside(nx1, ny1) == 1 && arr[nx1][ny1] == '#') //(nx1,ny1)가 벽을 만나면 못 움직임!
		{
			nx1 = x1; 
			ny1 = y1;
		}
		if (isinside(nx2, ny2) == 1 && arr[nx2][ny2] == '#') //(nx2,ny2)가 벽을 만나면 못 움직임!
		{
			nx2 = x2;
			ny2 = y2;
		}
		int tmp = go(cnt + 1, nx1, ny1, nx2, ny2); 
		if (tmp == -1) // -1 만나면 continue;
			continue;
		if (ans == -1 || ans > tmp) //버튼 누르는 '최소' 횟수를 반환해야 됨!
			ans = tmp;
	}
	return ans;
}

int main()
{
	F_I;
	int x1, x2, y1, y2;

	x1 = -1;
	x2 = -1;
	y1 = -1;
	y2 = -1;

	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			cin >> arr[i][j];
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (arr[i][j] == 'o')
			{
				if (x1 == -1)
				{
					x1 = i;
					y1 = j;
				}
				else
				{
					x2 = i;
					y2 = j;
				}
				arr[i][j] = '.'; //일단 동전이 있는 위치도 움직일수 있으므로 빈칸(.)으로 표시
			}
			
		}
	}
	cout << go(0, x1, y1, x2, y2) << '\n';
	return 0;
}

---

 

> 일단 main함수에서 동전 두개의 좌표를 각각 (x1,y1) (x2,y2)로 해 놓고, 어짜피 arr 보드판 자체는 매개변수로 보낼 필요가 없기 때문에(보드판에서 움직이는 정보는 동전들의 좌표가 유일하니까), 그 동전 두개의 좌표의 정보만 재귀함수의 매개변수로 보냈습니다. 

 

> isinside 함수를 통해 동전들이 arr 보드판 내에 있는지의 여부를 검사했습니다. 만약에 둘 다 보드판 밖에 있으면 안되니까, 그땐 -1을 반환하고, 만약 동전 두 개 중에 하나만 보드판 밖으로 나갔다면, 우리가 원하는 조건을 만족하는 상황이므로, 그때의 cnt(횟수)를 반환합니다. 이 cnt는 나중에 tmp 변수에 담겨서 ans와 최소값 비교를 하게 됩니다.

 

> 결론적으로 최솟값이 담긴 ans가 반환이 되고, 그것이 출력됩니다.