BOJ 13460 구슬 탈출 2 / C++

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

13460번: 구슬 탈출 2

백준 온라인저지 13460번 구슬 탈출 2 문제입니다.

 

아이디어

구슬 클래스를 하나 정의해서 대부분 해당 클래스에서 처리하도록 했고, BFS를 통해 최소거리를 찾았습니다.

문제의 핵심은 파란공이 들어갔을때에 대한 처리와 두 구슬을 움직이다 곂칠때에 대한 처리라고 생각했습니다.

파린공이 들어갔을때는 해당 케이스는 통과하도록 처리했고, 곂쳐질때는 이동거리가 더 긴공이 반대로 이동하도록 처리했습니다. 자세한건 아래 주석을 통해 확인할 수 있습니다.

#include <iostream>
#include <vector>
#include <queue>
#define MAX 10
using namespace std;

int mx[4] = { 0,1,0,-1 };
int my[4] = { 1,0,-1,0 };
int ry, rx, by, bx;
bool visited[10][10][10][10];
int n, m;

vector<vector<char>> field;

//dirction
enum {
	up = 0,
	right = 1,
	down = 2,
	left = 3
};

//field element
enum {
	Wall = '#',
	Hole = 'O',
	Red = 'R',
	Blue = 'B',
	None = '.'
};

//구슬
class Bead {
private:
	int y;
	int x;
	int dirCnt;
public:
	Bead() {}
	Bead(int a, int b , int c) {
		y = a;
		x = b;
		dirCnt = c;
	}

	//방향만 받아서 움직일수 있을때까지 움직임
	int move(int dir) {
		int moveCnt = 0;
		while (true) {
			//현재가 구멍일때
			if (field[y][x] == Hole) break;
			//다음이 벽일때
			if (field[y + my[dir]][x + mx[dir]] == Wall) break;
			y += my[dir];
			x += mx[dir];
			moveCnt++;
			
		}
		dirCnt++;
		return moveCnt;
	}	


	int getDircCnt() {
		return dirCnt;
	}

	int getX() {
		return x;
	}
	int getY() {
		return y;
	}
};


void setField() {
	field = vector<vector<char>>(n, vector<char>(m, ' '));
}

void input() {
	cin >> n >> m;
	setField();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> field[i][j];
			if (field[i][j] == Red) {
				ry = i;
				rx = j;
			}
			else if (field[i][j] == Blue) {
				by = i;
				bx = j;
			}

		}
	}
}

void bfs() {
	queue<pair<Bead, Bead>> q;
	q.push({ Bead(ry,rx,0),Bead(by,bx,0) });
	visited[ry][rx][by][bx] = true;
	while (!q.empty()) {
		Bead red = q.front().first;
		Bead blue = q.front().second;
		q.pop();

		if (red.getDircCnt() > 9) break;

		for (int i = 0; i < 4; i++) {
			Bead r = red;
			Bead b = blue;
			int rMove = r.move(i);
			int bMove = b.move(i);

			//파란구슬이 먼저 들어가면 처리하지 않음
			if (field[b.getY()][b.getX()] == Hole) continue;
			if (field[r.getY()][r.getX()] == Hole) {
				cout << r.getDircCnt();
				return;
			}

			//두 구슬이 곂쳐질때
			if (r.getY() == b.getY() && r.getX() == b.getX()) {

				//이동 거리가 더 많은 구슬이 한칸 반대로 움직임
				if (rMove > bMove) {
					r = Bead(r.getY() - my[i], r.getX() - mx[i], r.getDircCnt());
				}
				else {
					b = Bead(b.getY() - my[i], b.getX() - mx[i], b.getDircCnt());
				}
			}
			
			if (visited[r.getY()][r.getX()][b.getY()][b.getX()]) continue;
			visited[r.getY()][r.getX()][b.getY()][b.getX()] = true;
			q.push({ r,b });

		}
	}
	cout << "-1";
}

void solution() {
	bfs();
}

int main(void) {
	input();
	solution();
}