BOJ 13459, 13460, 15644 | 구슬 탈출 1, 2, 3

읽어보면 알겠지만 그냥 구현이다.
BFS인가 DFS인가 긴가민가했지만 깊이가 10밖에 안 되는 것을 보니 DFS 때리면 맞겠다 싶었다.

다들 구현이 어렵다고는 하는데 아마 공 2개가 충돌하는 경우 때문이 아닌가 싶다.

그래서 나는 Point 구조체를 만들어서 x, y 뿐만 아니라 moveable 변수도 넣어서 이 공이 벽에 부딪혀 있는지 아닌지 판정했다.

다른 공이 앞을 막고 있을 때, 만약 이 공이 moveable == 0 하다면 벽에 막혀있는 것이므로 움직일 가망이 없기 때문에 벽과 같은 취급을 해 주고, moveable == 1 하다면 다음 턴에 그 공이 움직일 것이기 때문에 그냥 한 턴 쉬었다.

구현 아이디어 자체는 쉬웠지만 DFS로 실행하면 루트 -> 리프까지는 문제가 없지만 탐색이 끝나고 되돌아와서 다른 경로로 갈 때 문제가 생긴다.

탐색하면서 board[][]를 수정했기 때문에 R과 B의 위치가 맞지 않게 되어 R과 B를 조정해주는 데 board를 전체 탐색하는 불상사가 생기는 것이다.

이를 해결하기 위해 dfs가 끝나면 R과 B를 board에서 빼고 dfs가 시작할 때 R과 B를 board에 놓아서 움직이는, 보드와 공을 분리해서 돌리는 방식을 채용했다.

개인적으로 재밌는 문제였다. 오랜만에 재밌는 구현 문제를 풀어본 느낌.

코드 (구슬 탈출 2는 여기서 출력만 수정하면 됨)

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio;cin.tie(nullptr);cout.tie(nullptr);

#define debug if constexpr (local) std::cout
#define endl '\n'

struct Point{
	int x, y;
	int moveable;
};

int xd[4] = {-1, 0, 1, 0};
int yd[4] = {0, 1, 0, -1};

char board[11][11];

int flag_red = 0;
int flag_blue = 0;

int resultdepth = INT_MAX;

int N, M;

void dfs(int depth, int dir, Point R, Point B){

	if (depth > 10) return;
	
	board[R.x][R.y] = 'R';
	board[B.x][B.y] = 'B';
	
	int i = dir;
	flag_red = 0; flag_blue = 0;
	while (true){
		
		/*
		for (int i = 0; i < N; i++){
			for (int j = 0; j < M; j++){
				debug << board[i][j];
			}
			debug << endl;
		}*/
		
		if (board[R.x + xd[i]][R.y + yd[i]] != '.'){ // if front not blank
			char front = board[R.x + xd[i]][R.y + yd[i]];
			//debug << front << " depth " << depth << endl;
			if (front == '#'){
				R.moveable = 0;
			}
			if (front == 'O'){
				R.moveable = 0;
				flag_red = 1;
				board[R.x][R.y] = '.';
			}
			if (front == 'B'){
				if (!B.moveable) R.moveable = 0;
			}
		}
		else{
			board[R.x][R.y] = '.';
			R.x += xd[i]; R.y += yd[i];
			board[R.x][R.y] = 'R';
		}
		
		if (board[B.x + xd[i]][B.y + yd[i]] != '.'){ // if front not blank
			char front = board[B.x + xd[i]][B.y + yd[i]];
			if (front == '#'){
				B.moveable = 0;
			}
			if (front == 'O'){
				B.moveable = 0;
				flag_blue = 1;
				board[B.x][B.y] = '.';
			}
			if (front == 'R'){
				if (!R.moveable) B.moveable = 0;
			}
		}
		else{
			board[B.x][B.y] = '.';
			B.x += xd[i]; B.y += yd[i];
			board[B.x][B.y] = 'B';
		}
		
		
		if (!R.moveable && !B.moveable){
			break;
		}
	}
	
	// board clear;
	if (board[R.x][R.y] == 'R') board[R.x][R.y] = '.';
	if (board[B.x][B.y] == 'B') board[B.x][B.y] = '.';
	
	if (flag_red && !flag_blue){
		// success
		resultdepth = min(resultdepth, depth);
	}
	else if (!flag_red && !flag_blue){
		for (int j = 0; j < 4; j++)
			dfs(depth+1, j, {R.x, R.y, 1}, {B.x, B.y, 1});
	}
}

int main(){
	FASTIO;
	
	cin >> N >> M;
	cin.ignore();
	
	Point R = {0,0,1}, B = {0,0,1};
	
	for (int i = 0; i < N; i++){
		string line; getline(cin, line);
		for (int j = 0; j < M; j++){
			board[i][j] = line[j];
			if (line[j] == 'R'){
				R.x = i; R.y = j;
			}
			else if (line[j] == 'B'){
				B.x = i; B.y = j;
			}
			
		}
	}
	
	dfs(1, 0, R, B);
	dfs(1, 1, R, B);
	dfs(1, 2, R, B);
	dfs(1, 3, R, B);
	
	if (resultdepth == INT_MAX) cout << 0;
	else cout << 1;
	
}