[C++]백준16197번 두 동전

오늘은 백준16197번 두 동전 문제를 풀어보도록 하자.

일반적인 BFS문제이지만 큐 관리를 해주어야했다. 한 번에 두 동전이 움직이므로 하나씩 하지 않고 큐에 두 동전의 위치를 한 번에 넣어주었다.

메모리적인 부분이 마음에 들진 않았다. 백트래킹적인 요소가 몇 가지 들어가야하는데 만일 움직인 횟수가 10번이 넘어가면 -1을 리턴하고 동전의 위치가

같다면 continue를 해주어 연산의 횟수를 최소화 했다.

문제는 다음과 같다.

                               [접근법]

  1. 두 동전의 위치를 한 번에 저장해준다.
  
  2. dir배열을 이용하여 움직임을 구현하였고 만일 움직인 곳에 '#' 이 있으면 다시 dir배열만큼 빼주었다.
  
  3. 그리고 동전의 위치가 같다면 하나의 동전만 떨어질 수 없으므로 continue하여 연산 최소화.
  
  4. cnt가 10번이 넘어가면 return -1
  
  5. 만일 하나만 떨어졌다면 return cnt를 하여 바로 출력해주었다.

                                     [코드]
#include <iostream>
#include <queue>
using namespace std;

int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
char map[21][21];
int R, C, cnt = 0,a, b, c, d;
bool flag = true;

struct pos {
	int y_1;
	int x_1;
	int y_2;
	int x_2;
};
queue<pos>Q;

int bfs() {
	while (!Q.empty()) {
		int size_of_Q = Q.size();
		cnt++;

		if (cnt > 10) {
			return -1;
		}
		for (int k = 0; k < size_of_Q; k++) {
			int y_1 = Q.front().y_1;
			int x_1 = Q.front().x_1;
			int y_2 = Q.front().y_2;
			int x_2 = Q.front().x_2;

			Q.pop();

			for (int i = 0; i < 4; i++) {
				int my_1 = y_1 + dir[i][0];
				int mx_1 = x_1 + dir[i][1];
				int my_2 = y_2 + dir[i][0];
				int mx_2 = x_2 + dir[i][1];

				if (map[my_1][mx_1] == '#') {
					my_1 -= dir[i][0];
					mx_1 -= dir[i][1];
				}
				if (map[my_2][mx_2] == '#') {
					my_2 -= dir[i][0];
					mx_2 -= dir[i][1];
				}

				if (my_1 == my_2 && mx_1 == mx_2) {
					continue;
				}
				if (my_1 < 1 || mx_1 < 1 || my_1 > R ||
					mx_1 > C) {
					if (my_2 >= 1 && mx_2 >= 1 && my_2 <= R &&
						mx_2 <= C) {
						return cnt;
					}
				}
				if (my_2 < 1 || mx_2 < 1 || my_2 > R ||
					mx_2 > C) {
					if (my_1 >= 1 && mx_1 >= 1 && my_1 <= R &&
						mx_1 <= C) {
						return cnt;
					}
				}
				if (my_1 >= 1 && my_1 <= R &&
					my_2 >= 1 && my_2 <= R &&
					mx_1 >= 1 && mx_1 <= C &&
					mx_2 >= 1 && mx_2 <= C) {
					Q.push({ my_1, mx_1, my_2,mx_2 });
				}
			}
		}
	}
}

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

	cin >> R >> C;

	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			cin >> map[i][j];
			if (map[i][j] == 'o' && flag) {
				a = i; b = j;
				flag = false;
			}
			else if (map[i][j] == 'o' && !flag) {
				c = i; d = j;
			}
		}
	}

	Q.push({ a,b,c,d });
	cout << bfs();
}