[백준] 16197 두 동전

[백준] 16197 두 동전

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

#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <iostream>
using namespace std;

int N, M;
vector<vector<int>> board;

int dirR[4] = { 0, 0, 1, -1 };
int dirC[4] = { 1, -1, 0, 0 };

bool inRange(pair<int, int> pos) {
	int r = pos.first;
	int c = pos.second;
	if (r < 0 || r >= N) return false;
	if (c < 0 || c >= M) return false;
	return true;
}

struct state {
	pair<int, int> coin1;
	pair<int, int> coin2;
	vector<vector<int>> curBoard;

	bool operator<(const state& s) const {
		return coin1 < s.coin1;
	}
};

int solve(pair<int, int> coin1, pair<int, int> coin2) {
	priority_queue <pair<int,state>> q;
	q.push({ 0, {coin1, coin2, board} });

	set <pair<pair<int, int>, pair<int, int>>> visited;

	while (!q.empty()) {
		int curMoves = -q.top().first;
		state curState = q.top().second;
		q.pop();

		if (visited.find({ curState.coin1, curState.coin2 }) != visited.end()) continue;
		visited.insert({ curState.coin1, curState.coin2 });

		//10번보다 많이 이동해야하는 경우 종료
		if (curMoves == 10) {
			return -1;
		}

		for (int d = 0; d < 4; ++d) {
			pair<int, int> nextCoin1;
			pair<int, int> nextCoin2;

			nextCoin1.first = curState.coin1.first + dirR[d];
			nextCoin1.second = curState.coin1.second + dirC[d];
			nextCoin2.first = curState.coin2.first + dirR[d];
			nextCoin2.second = curState.coin2.second + dirC[d];
			
			//둘 다 보드에서 떨어트림 -> 실패
			if (!inRange(nextCoin1) && !inRange(nextCoin2)) continue;

			//하나의 동전만 떨어트림 -> 성공
			if ((inRange(nextCoin1) && !inRange(nextCoin2)) || (!inRange(nextCoin1) && inRange(nextCoin2))) {
				//priority_queue를 사용했기 때문에 가장 먼저 찾은 답이 최소 답
				return curMoves + 1;
			}

			//둘 다 보드에서 안떨어짐 -> 두 동전 동시에 이동

			//이동하려는 칸 벽인 경우 이동하지 X
			bool moveCoin1 = true; 
			bool moveCoin2 = true;
			if (curState.curBoard[nextCoin1.first][nextCoin1.second] == -1) {
				moveCoin1 = false;
				nextCoin1 = curState.coin1;
			}
			if (curState.curBoard[nextCoin2.first][nextCoin2.second] == -1) {
				moveCoin2 = false;
				nextCoin2 = curState.coin2;
			}

			//두 동전 모두 이동할 수 없는 경우 건너뜀
			if (!moveCoin1 && !moveCoin2) continue;

			//방문하지 않은 상태인지 확인
			if (visited.find({ nextCoin1,nextCoin2 }) != visited.end()) continue;

			//동전 이동
			if (moveCoin1) {
				curState.curBoard[curState.coin1.first][curState.coin1.second]--;
				curState.curBoard[nextCoin1.first][nextCoin1.second]++;
			}
			if (moveCoin2) {
				curState.curBoard[curState.coin2.first][curState.coin2.second]--;
				curState.curBoard[nextCoin2.first][nextCoin2.second]++;
			}
			
			q.push({ -(curMoves + 1), {nextCoin1, nextCoin2, curState.curBoard} });

			//동전 원상복귀
			if (moveCoin1) {
				curState.curBoard[curState.coin1.first][curState.coin1.second]++;
				curState.curBoard[nextCoin1.first][nextCoin1.second]--;
			}
			if (moveCoin2) {
				curState.curBoard[curState.coin2.first][curState.coin2.second]++;
				curState.curBoard[nextCoin2.first][nextCoin2.second]--;
			}

		}
	}
	//동전을 떨어뜨릴 수 없는 경우
	return -1;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> M;

	//두 동전의 좌표
	vector<pair<int, int>> coin;
	for (int i = 0; i < N; ++i) {
		board.push_back(vector<int>());

		string input;
		cin >> input;

		for (int j = 0; j < M; ++j) {
			//벽 -1 빈칸 0 동전 1
			if (input[j] == '#') {
				board[i].push_back(-1);
			}
			else if (input[j] == '.') {
				board[i].push_back(0);
			}
			else if (input[j] == 'o') {
				board[i].push_back(1);
				//동전 위치 저장
				coin.push_back({ i, j });
			}
		}
	}

	cout <<	solve(coin[0], coin[1]);
	
	return 0;
}

• 반례

3 2
##
o#
o#
.#
.#
.#
.#
.#
.#
.#
.#
.#
.#


출력: 11
답: -1