13460 구슬 탈출 2

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

13460번: 구슬 탈출 2

처음엔 불 문제와 마찬가지로 각각 BFS를 돌려서 출력을 내려고 했는데 이렇게 할 경우 두 구슬이 서로 다른 방향으로 기울어지는 문제가 생긴다. 여기에서 맘이 꺾여서 포기하고 다른 블로그와 답지를 확인해 보았다.

//https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0D/solutions/13460.cpp
#include <bits/stdc++.h>
#define X second
#define Y first
using namespace std;

int N,M;
pair<int,int> red,blue;
char board[12][12];
int dist[12][12][12][12];
int dy[4]={1,0,-1,0};
int dx[4]={0,1,0,-1};

int bfs(){
	queue<tuple<int,int,int,int>> Q;
	Q.push(make_tuple(red.Y,red.X,blue.Y,blue.X));
	dist[red.Y][red.X][blue.Y][blue.X]=0;
	while(!Q.empty()){
		auto cur=Q.front(); Q.pop();
		int ry,rx,by,bx; tie(ry,rx,by,bx)=cur;
		int cnt=dist[ry][rx][by][bx];
		
		//0부터 시작이므로 cnt가 10이면 11회차임
		if(cnt>=10) return -1;
		
		for(int dir=0;dir<4;dir++){
			int n_ry=ry; int n_rx=rx;
			int n_by=by; int n_bx=bx;
			
			//Blue BFS 실행 
			while(board[n_by+dy[dir]][n_bx+dx[dir]]=='.'){
				n_by+=dy[dir]; n_bx+=dx[dir];
			}
			
			//Blue 탈출했으면 continue.
			if(board[n_by+dy[dir]][n_bx+dx[dir]]=='O') continue;
			
			//Red BFS 실행
			while(board[n_ry+dy[dir]][n_rx+dx[dir]]=='.'){
				n_ry+=dy[dir]; n_rx+=dx[dir];
			}
			
			//Red 탈출했으면 끝 
			if(board[n_ry+dy[dir]][n_rx+dx[dir]]=='O') return cnt+1;
			
			//Red Blue 겹쳐있을 경우
			if((n_ry==n_by)&&(n_rx==n_bx)){ //위 오른쪽 아래 왼쪽 
				if(dir==0) ry<by ? n_ry-- : n_by--;
				else if(dir==1) rx<bx ? n_rx-- : n_bx--;
				else if(dir==2) ry>by ? n_ry++ : n_by++;
				else if(dir==3) rx>bx ? n_rx++ : n_bx++;
			}
			
			//이미 방문한 적이 있다면 continue;
			if(dist[n_ry][n_rx][n_by][n_bx]!=-1) continue;
			
			//아니면 Q에 push하고 dist 설정 
			Q.push(make_tuple(n_ry,n_rx,n_by,n_bx));
			dist[n_ry][n_rx][n_by][n_bx]=cnt+1;
		}
	}	
	return -1;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>N>>M;
	for(int i=0;i<10;i++)
		for(int j=0;j<10;j++)
			for(int k=0;k<10;k++)
				for(int r=0;r<10;r++)
					dist[i][j][k][r]=-1;
					
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			cin>>board[i][j];
			if(board[i][j]=='B'){
				blue={i,j};
				board[i][j]='.';
			}
			if(board[i][j]=='R'){
				red={i,j};
				board[i][j]='.';
			}
		}
	}
			
	cout<<bfs();
	return 0;
}

 

동시에 움직이는 문제는 이게 처음이었는데 공부가 많이 되었다.