[백준] 16197 두 동전

문제

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

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

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

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

입력

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

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

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

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

출력

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

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL)
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 };
int N, M, mv = 12;
char mp[21][21];
vector<pi>coin;

void dfs(pi a,pi b,int k) {
	if (k == 11)return;
	
	rep(i, 4) {
		int aout = 0, bout = 0;
		int ny = a.first + dy[i];
		int nx = a.second + dx[i];
		if (ny < 0 || ny >= N || nx < 0 || nx >= M)aout = 1;
		else if (mp[ny][nx] == '#') { ny = a.first; nx = a.second; }

		int nny = b.first + dy[i];
		int nnx = b.second + dx[i];
		if (nny < 0 || nny >= N || nnx < 0 || nnx >= M)bout = 1;
		else if (mp[nny][nnx] == '#') { nny = b.first; nnx = b.second; }

		if (aout && bout) {
			continue;
		}
		else if (aout || bout) {
			mv = min(mv, k);
			continue;
		}
		dfs({ ny,nx}, {nny,nnx }, k + 1);
	}
}
int main() {
	FAST;
	cin >> N >> M;
	rep(i, N)rep(j, M) {
		cin >> mp[i][j];
		if (mp[i][j] == 'o') {
			mp[i][j] = '.';
			coin.push_back({ i,j });
		}
	}
	dfs(coin[0],coin[1],1);
	mv == 12 ? cout << -1 : cout << mv;
}

백트래킹 문제입니다.

총 10번까지 움직이면서 동전 둘중 하나가 떨어지는지, 모두 떨어지는지 확인하며 백트래킹을 진행합니다.

만약 모두 떨어지거나 하나만 떨어지는경우 continue하고,

그게 아니라면 깊이++를 합니다.