두 동전

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	9745	4287	2903	42.250%

문제

N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다.

보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다.

두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, 두 동전의 위치는 다르다.

버튼은 “왼쪽”, “오른쪽”, “위”, “아래”와 같이 4가지가 있다.

버튼을 누르면 두 동전이 버튼에 쓰여 있는 방향으로 동시에 이동하게 된다.

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

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

입력

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

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

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

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

출력

첫째 줄에 두 동전 중 하나만 보드에서 떨어뜨리기 위해 눌러야 하는 버튼의 최소 횟수를 출력한다.

만약, 두 동전을 떨어뜨릴 수 없거나, 버튼을 10번보다 많이 눌러야 한다면, -1을 출력한다.

예제 입력 1

1 2
oo

예제 출력 1

1

예제 입력 2

6 2
.#
.#
.#
o#
o#
##

예제 출력 2

3

예제 입력 3

6 2
..
..
..
o#
o#
##

예제 출력 3

3

예제 입력 4

5 3
###
.o.
###
.o.
###

예제 출력 4

-1

예제 입력 5

5 3
###
.o.
#.#
.o.
###

예제 출력 5

3

출처

• 문제를 번역한 사람: baekjoon

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 백트래킹

---

통과된 코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int _N, _M, _Res = -1;
int _DxDy[4][2] = { { 1, 0}, { 0, -1}, { 0, 1}, { -1, 0} };
char _Map[20][20];
string _Str;

vector<pair<int,int>> _Coins;

struct CntPos
{
	pair<int,int> CoinOne;
	pair<int,int> CoinTwo;
	int Cnt;

	CntPos(int _x1, int _y1, int _x2, int _y2, int _cnt) 
		: CoinOne(make_pair(_x1, _y1)), CoinTwo(make_pair(_x2, _y2)), Cnt(_cnt) {}
};

queue<CntPos> BfsQueue;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> _N >> _M;
	for (int i = 0; i < _N; i++) {
		cin >> _Str;
		for (int j = 0; j < _M; j++) {
			_Map[i][j] = _Str[j];
			if (_Str[j] == 'o')
				_Coins.push_back({ i, j });
		}
	}

	BfsQueue.push(CntPos(_Coins[0].first, _Coins[0].second, _Coins[1].first, _Coins[1].second, 0));
	while (!BfsQueue.empty()) {
		CntPos _cntpos = BfsQueue.front();
		BfsQueue.pop();

		for (int i = 0; i < 4; i++) {
			bool CheckOne = false, CheckTwo = false;
			_Coins[0].first = _cntpos.CoinOne.first + _DxDy[i][0];
			_Coins[0].second = _cntpos.CoinOne.second + _DxDy[i][1];
			_Coins[1].first = _cntpos.CoinTwo.first + _DxDy[i][0];
			_Coins[1].second = _cntpos.CoinTwo.second + _DxDy[i][1];

			// 동전의 위치가 같다면 하나만 떨어뜨리는 조건에 맞지 않는다.
			if (_Coins[0] == _Coins[1]) continue;

			// 두 동전 중 하나만 보드에서 떨어뜨리기 위함
			if (_Coins[0].first < 0 || _Coins[0].second < 0 || _Coins[0].first >= _N || _Coins[0].second >= _M)
				CheckOne = true;
			if (_Coins[1].first < 0 || _Coins[1].second < 0 || _Coins[1].first >= _N || _Coins[1].second >= _M)
				CheckTwo = true;

			// 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.
			if (!CheckOne && (_Map[_Coins[0].first][_Coins[0].second] == '#')) {
				_Coins[0].first = _cntpos.CoinOne.first;
				_Coins[0].second = _cntpos.CoinOne.second;
			}
			if (!(CheckTwo) && _Map[_Coins[1].first][_Coins[1].second] == '#') {
				_Coins[1].first = _cntpos.CoinTwo.first;
				_Coins[1].second = _cntpos.CoinTwo.second;
			}

			int _TCnt = _cntpos.Cnt;
			if (_TCnt >= 10) {
				_Res = -1;
				while (!BfsQueue.empty())
					BfsQueue.pop();
				break;
			}

			if (CheckOne ^ CheckTwo) {
				_Res = _TCnt + 1;
				while (!BfsQueue.empty())
					BfsQueue.pop();
				break;
			}
			else if(CheckOne && CheckTwo)
				continue;

			BfsQueue.push(CntPos(_Coins[0].first, _Coins[0].second, _Coins[1].first, _Coins[1].second, _TCnt + 1));
		}
	}

	cout << _Res;
	return 0;
}

생각보다 메모리를 많이 사용…

DFS 탐색을 이용한 백트레킹 방법이 시간과 메모리 부분에서 더 효율적이다.

---

DFS 참고 코드

https://hyeo-noo.tistory.com/126

#include <iostream>
#include <queue>
#include <cstring>
 
#define pii pair<int, int>
 
using namespace std;
 
 
int N, M, result = 1e9+7;
int Map[21][21];    // 2 : 동전 위치   0 : 벽 위치   1 : 빈칸
vector< pii > startP;
int dr[4] = {0, 0, 1, -1}, dc[4] = {1, -1, 0, 0};
 
void input(){
    // Map에서 벗어나는 경우는 -1로 설정
    memset(Map, -1, sizeof(Map));
    
    cin >> N >> M;
    string str;
    for(int i = 1; i <= N; i++){
        cin >> str;
        for(int j = 0; j < M; j++){
            if(str[j] == 'o'){
                Map[i][j+1] = 2;
                startP.push_back({i, j+1});
            }
            else if(str[j] == '#') Map[i][j+1] = 0;
            else Map[i][j+1] = 1;
        }
    }
}
 
bool isOut(const pii &A){
    if(A.first < 1 || A.first > N || A.second < 1 || A.second > M) return true;
    return false;
}
 
void dfs(pii A, pii B, int cnt){
    // 현재 result보다 cnt가 크다면 더이상의 탐색은 불필요
    if(result < cnt) return;
    
    // cnt 가 10보다 커지면 result값 갱신
    if(cnt > 10){
        result = min(result, cnt);
        return;
    }
    
    // 둘 다 떨어졌으면 되돌아감
    if(isOut(A) && isOut(B)) return;
    // 하나만 떨어졌으면 result를 최소 cnt값으로 교체
    else if((isOut(A) && !isOut(B)) || (!isOut(A) && isOut(B))){
        result = min(result, cnt);
        return;
    }
    
    for(int i = 0; i < 4; i++){
        pii An = {A.first + dr[i], A.second + dc[i]};
        pii Bn = {B.first + dr[i], B.second + dc[i]};
        if(!Map[An.first][An.second]) An = A;
        if(!Map[Bn.first][Bn.second]) Bn = B;
        
        dfs(An, Bn, cnt+1);
    }
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    input();
    dfs(startP[0], startP[1], 0);
    
    if(result > 10) cout << -1;
    else cout << result;
    
    return 0;
}