문제

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

---

풀이

동전이 이동할 수 있는 모든 방향에 대해 탐색을 진행하다가, 더 이상 유망하지 않으면 가지치기 하는 백트래킹 문제였다.

여기서 더 이상 유망하지 않은 경우는 다음과 같이 정리할 수 있다.

동전 두개가 모두 떨어진 경우

현위치에서 더 이상 다른 방향으로 이동할 필요가 없다. (우리가 원하는, 동전 한 개만 떨어지는 상황이 아니므로)

그리고 이동 횟수의 최솟값도 갱신하지 않는다.

// 동전 두개 모두 떨어진 경우
if(isRangeOver(nax, nay) && isRangeOver(nbx, nby)) return;

동전 하나만 떨어진 경우

우리가 원하는 상황이므로 이동 횟수의 최솟값을 갱신하고, 그 다음 경우의 수에 대한 탐색을 진행한다.

// 동전 A만 떨어진 경우 
if(isRangeOver(nax, nay) && !isRangeOver(nbx, nby)){
	answer = min(answer, cnt);
	return; 
}

// 동전 B만 떨어진 경우 
if(!isRangeOver(nax, nay) && isRangeOver(nbx, nby)){
	answer = min(answer, cnt);
	return; 
}

이동 횟수가 최솟값이 아닌 경우

동전이 하나만 떨어지는 경우이긴 한데, 이동 횟수가 최솟값이 아니면 더 이상 탐색을 진행할 필요가 없다.

if(answer < cnt) return; 

이동 횟수가 10번을 넘은 경우 (두 동전 모두 떨어지지 않은 상태)

마지막 이동 횟수가 10번인 경우, 최솟값을 갱신하고 다른 경우의 수로 넘어간다. 여기서 더 탐색을 진행하면 이동 횟수가 10번을 넘어가기 때문이다.

if(cnt > 10){
	answer = min(answer, cnt);
	return; 
}

그리고 탐색의 시작점이 되는 '두 동전의 위치'는 입력 받을 때 벡터에 따로 저장해둔다!

---

C++ 코드

참고: https://yabmoons.tistory.com/61

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <map> 
using namespace std;
typedef pair<int, int> pii; 
typedef long long ll;

const int MAX = 21; 
int N, M; 
int answer = 1e9; 
char graph[MAX][MAX]; 
vector<pii> coin;

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

void input() {
	cin >> N >> M; 

	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			cin >> graph[i][j]; 

			// 두 동전의 위치 저장 (탐색의 시작점)
			if(graph[i][j] == 'o'){
				coin.push_back({i, j});
			}
		}
	}
}

bool isRangeOver(int x, int y) {
	return (x < 0 || x >= N || y < 0 || y >= M);
}

// 두 동전의 좌표, 이동 횟수 (버튼 누른 횟수), 이동 방향 
void dfs(pii coinA, pii coinB, int cnt, int dir){
	// 기존의 최솟값 보다 많이 눌리면 
	// 다음 경우의 수로 pass 
	if(answer < cnt) return; 

	// 마지막 이동 횟수가 10번인 경우
	// 최솟값 갱신 후 다음 경우의 수로 pass
	if(cnt > 10){
		answer = min(answer, cnt);
		return; 
	}

	int ax = coinA.first, ay = coinA.second; 
	int bx = coinB.first, by = coinB.second; 
	
	int nax = ax + dx[dir];
	int nay = ay + dy[dir];

	int nbx = bx + dx[dir];
	int nby = by + dy[dir];

	// 동전 두개 모두 떨어진 경우
	if(isRangeOver(nax, nay) && isRangeOver(nbx, nby)) return;

	// 동전 A만 떨어진 경우 
	if(isRangeOver(nax, nay) && !isRangeOver(nbx, nby)){
		answer = min(answer, cnt);
		return; 
	}

	// 동전 B만 떨어진 경우 
	if(!isRangeOver(nax, nay) && isRangeOver(nbx, nby)){
		answer = min(answer, cnt);
		return; 
	}

	// 두개의 동전 모두 떨어지지 않은 경우
	// 계속해서 이동한다.

	// 벽을 만난 경우 이동하지 못한다. 
	if(graph[nax][nay] == '#'){
		nax = ax; 
		nay = ay; 
	}

	if(graph[nbx][nby] == '#'){
		nbx = bx; 
		nby = by; 
	}

	// 그 다음 방향에 대한 탐색 진행 
	for(int i = 0; i < 4; i++){
		dfs({nax, nay}, {nbx, nby}, cnt + 1, i);
	}
}

void solution() {
	for(int i = 0; i < 4; i++){
		dfs(coin[0], coin[1], 1, i);
	}

	if(answer > 10) answer = -1;
	cout << answer; 
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	input(); 
	solution();

	return 0; 
}