[백준 16197] 두 동전

● 문제 : 백준 16197번 : 두 동전

16197번: 두 동전

 

● 알고리즘

- 백트래킹

 

● 문제 풀이

백트래킹을 이용하여 문제를 풀었다. 보드판의 정보를 입력받을 N과 M 그리고 이차원문자열벡터 arr, 처음 동전 2개의 좌표를 입력받을 coin1과 coin2, 동전을 상하좌우로 이동시키므로 이동방향을 저장하는 배열 dir, 문제의 조건에 만족하는 최소의 답을 저장하는 ans를 전역변수로 선언하고 시작한다. 

처음 보드판의 정보를 입력받고, 동전의 위치를 나타내는 'o'를 입력받았다면 각각 coin1과 coin2에 좌표의 정보를 저장한다. DFS 함수를 통해 답을 구하는데 여기서 매개변수는 coin1과 coin2 그리고 동전을 이동시킨 횟수를 나타내는 cnt로 하였다. 처음에 cnt를 0으로 설정하고 진행하였더니 마지막 이동횟수를 추가하지 못해 답이 1씩 모자르게 나왔다. 그래서 처음 cnt값을 1로 설정하였다. 

DFS 함수가 호출되면 이차원 배열 dir을 통해 동전이 다음에 위치할 좌표를 설정한다. 그 다음 다음에 위치할 좌표가 보드판을 벗어나는지 아닌지 check 함수를 통해 검사를 해주는데, 두 동전이 모두 보드판을 벗어난다면 문제의 조건에 알맞지 않으므로 무시하고 진행한다. 이를 위해 continue를 적어주었다. 만약 두 동전 중 하나의 동전만 보드판을 벗어난다면 문제의 조건에 알맞으므로, 현재의 cnt 값 즉, 동전을 이동시킨 횟수가 답이 될 수 있으므로 ans값과 비교하여 작은 값을 ans에 저장한다. 만약 두 동전이 모두 보드판을 벗어나지 않는다면 각각의 동전이 다음에 위치할 좌표가 벽인지 아닌지 block 함수를 통해 검사를 해준다. 만약 다음에 위치할 좌표가 벽이라면 이동할 수 없으므로, 원래 위치로 동전을 보내준다. 그 다음 DFS 함수를 재귀로 호출하여 답을 구해준다. 

재귀함수를 호출할 때 가장 중요한 것이 탈출조건이다. 만약 탈출조건이 없다면 이 재귀함수는 끝나지 않고 무한히 실행될 것이다. 문제에 동전을 떨어뜨릴 수 없거나 버튼을 10번보다 많이 눌러야 한다면 -1을 출력한다는 조건이 있다. 따라서, 재귀함수를 계속 돌다가 cnt 값이 10을 초과하거나 최소 이동횟수인 ans 값보다 크다면 함수를 탈출한다. 마지막에 정답을 출력할 때 ans 값이 10보다 크다면 -1로 값을 바꿔준다. 

많은 백트래킹 문제를 풀었는데, 그래프 문제에서 자주 다뤘던 좌표를 이용하는 문제라 그런지 탈출조건을 설정하는 것 말고는 어렵지 않게 해결했다. 

 

● 코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <algorithm>
#include <string>
#include <cstring>
#include <climits>
#include <random>
#include <cmath>
#include <set>
#include <ctime>
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;

int N, M;
vector<vector<char>>arr(21, vector<char>(21));
ii coin1, coin2;
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
int ans = INT_MAX;
bool check(ii a)
{
	if (0 <= a.first && a.first < N && 0 <= a.second && a.second < M)
		return true;
	else
		return false;
}
bool block(ii a)
{
	if (arr[a.first][a.second] == '#')
		return true;
	else
		return false;
}
void DFS(ii c1, ii c2, int cnt)
{
	if (ans < cnt || cnt > 10)
		return;

	for (int i = 0; i < 4; i++)
	{
		ii nc1 = { c1.first + dir[i][0],c1.second + dir[i][1] };
		ii nc2 = { c2.first + dir[i][0],c2.second + dir[i][1] };
		if (!check(nc1) && !check(nc2))
			continue;
		else if ((check(nc1) && !check(nc2)) || (!check(nc1) && check(nc2)))
		{
			if (cnt < ans)
				ans = cnt;
			return;
		}
		else
		{
			if (block(nc1))
				nc1 = c1;
			if (block(nc2))
				nc2 = c2;
			DFS(nc1, nc2, cnt + 1);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> N >> M;
	int cnt = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> arr[i][j];
			if (arr[i][j] == 'o')
			{
				if (cnt == 0)
				{
					coin1.first = i, coin1.second = j;
					cnt++;
				}
				else
					coin2.first = i, coin2.second = j;
			}
		}
	}

	DFS(coin1, coin2, 1);
	if (ans > 10)
		ans = -1;
	cout << ans;
	return 0;
}