[백준/c++] BOJ 16197 - 두 동전

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

16197번: 두 동전

 

 

문제 설명

NxM 크기의 보드와 4개의 버튼, 두 개의 동전이 있다.

두 동전은 다른 위치에 존재하며, 버튼을 이용해 위, 아래, 오른쪽, 왼쪽으로 두 동전이 동시에 한칸 움직인다.

이동하려는 곳에 벽이 있으면 이동하지 않으며, 이동하려는 방향에 칸이 없으면 동전을 보드 바깥으로 떨어진다.

하나의 동전만 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야 하는지 구한다. 단, 두 동전을 떨어뜨릴  없거나, 버튼을 10번보다 많이 눌러야 한다면 -1을 출력한다.

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

N, M (1 <= N, M <= 20)

 

해결

상당히 간단한 bfs 문제이다. 상하좌우 모두 방문하여 두 동전 중 하나만 떨어뜨릴 수 있는 경로를 찾는다.

다만, 경로가 10보다 길다면 -1을 출력한다.

또한 두 동전이 모두 떨어질 수밖에 없다면  -1을 출력한다.

 

구현할 때는 queue 안에 tuple로 동전 두 개의 좌표와 움직인 횟수를 넣어 주었다.

두 동전의 좌표를 이동시키며 두 동전이 떨어지지 않은 경우 움직인 횟수를 1 더하여 queue 안에 다시 넣어 주었다.

 

 

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int n, m, ck = 1;
char board[21][21];
int ans = 11;
pair<int, int> one, two;
int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };

int range(int x, int y) {
	return (x < 0 || x >= n || y < 0 || y >= m);
}

void bfs() {
	queue<tuple<pair<int, int>, pair<int, int>, int>> q;
	q.push({ one,two, 0 });
	while (!q.empty()) {
		auto cur = q.front(); q.pop();
		if (get<2>(cur) >= 10) continue;

		for (int i = 0; i < 4; i++) {
			int one_nx = get<0>(cur).x + dx[i], one_ny = get<0>(cur).y + dy[i];
			int two_nx = get<1>(cur).x + dx[i], two_ny = get<1>(cur).y + dy[i];

			if (board[one_nx][one_ny] == '#') {
				one_nx = get<0>(cur).x;
				one_ny = get<0>(cur).y;
			}
			if (board[two_nx][two_ny] == '#') {
				two_nx = get<1>(cur).x;
				two_ny = get<1>(cur).y;
			}

			if (range(one_nx, one_ny) && range(two_nx, two_ny)) continue;

			if (!range(one_nx, one_ny) && range(two_nx, two_ny)) {
				ans = min(ans, get<2>(cur) + 1);
				if (get<2>(cur) + 1 == ans)
				continue;
			}
			else if (range(one_nx, one_ny) && !range(two_nx, two_ny)) {
				ans = min(ans, get<2>(cur) + 1);
				continue;
			}

			q.push({ { one_nx, one_ny }, { two_nx, two_ny }, get<2>(cur) + 1 });
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
			if (board[i][j] == 'o') {
				if (ck) {
					one = make_pair(i, j);
					ck = 0;
				}
				else two = make_pair(i, j);
			}
		}
	}
	bfs();
	if (ans >= 11) cout << "-1";
	else
		cout << ans;
}