[BOJ] 백준 13460번: 째로탈출 2

째로탈출 2

문제

N*M 보드에 파란 구슬 빨간 구슬 구멍이 한 개씩 있고, 상하좌우 4방향으로 기울일 수 있을 때, 최소 몇 번 만에 빨간 구슬이 구멍에 나올 수 있는지 출력하는 문제이다. 단, 파란 구슬이 구멍으로 같이 나오면 실패이다.

문제 풀이

최대 10번 까지 보드를 조작할 수 있으므로, BFS 탐색을 이용하면 각 상태 공간에서 상하좌우 4방향으로 전이 가능 하고, 한 상태 공간에서 해당 방향으로 최대 \(max(N,M)\) 만큼 이동할 수 있으므로 \(O(4^{10} max(N,M))\) 임을 알 수 있다. 따라서 각 상태 공간 내에서 한 방향으로 이동 할 때

1. 빨간 구슬과 파란 구슬이 일직선 상에 없음

1.1) 빨간 구슬이 가는 길에 구멍이 있는 경우 --> 탈출 성공

1.2) 파란 구슬이 가는 길에 구멍이 있는 경우 --> 탈출 실패

1.3) 구멍이 없는 경우 --> 구슬들을 최대한 이동한 후 큐에 push

2. 빨간 구슬이 가는 길에 파란 구슬이 있는 경우

2.1) 파란 구슬 앞에 구멍이 있는 경우 --> 탈출 성공

2.2) 파란 구슬 뒤에 구멍이 있는 경우 --> 탈출 실패

2.3) 구멍이 없는 경우 --> 파란 구슬은 최대한 이동, 빨간 구슬은 한 칸 덜 이동한 후에 큐에 push

3. 파란 구슬이 가는 길에 빨간 구슬이 있는 경우

3.1) 구멍이 있는 경우 --> 탈출 실패

3.2) 구멍이 없는 경우 --> 빨간 구슬은 최대한 이동, 파란 구슬은 한 칸 덜 이동한 후에 큐에 push

위의 과정을 bfs 각 상태 공간마다 시행하고 깊이가 10이 되면 종료하게 구현하면 된다.

 

소스 코드

	#include <bits/stdc++.h>
	using namespace std;
	struct Node{
	int d, rx, ry, bx, by;
	};
	char mat[10][11];
	int n, m;
	int fx, fy;
	int dx[4]={-1, 1, 0, 0};
	int dy[4]={0, 0, -1, 1};
	int main(){
	scanf("%d%d", &n, &m);
	for(int i=0;i<n;i++)
	scanf("%s", mat[i]);
	int srx, sry, sbx, sby;
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
	if(mat[i][j]=='R')
	srx=i, sry=j;
	else if(mat[i][j]=='B')
	sbx=i, sby=j;
	else if(mat[i][j]=='O')
	fx=i, fy=j;
	queue<Node> q;
	q.push({0, srx, sry, sbx, sby});
	int ans=-1;
	while(!q.empty()){
	int cnt=q.front().d;
	int rx=q.front().rx;
	int ry=q.front().ry;
	int bx=q.front().bx;
	int by=q.front().by;
	q.pop();
	if(cnt==10)
	break;
	for(int i=0;i<4;i++){
	//빨간 공이 굴러가는 경우에서
	int rex=0;
	int blue=0;
	int nrx, nry;
	int rmove=0;
	nrx=rx+dx[i];
	nry=ry+dy[i];
	while(mat[nrx][nry]!='#'){
	rmove++;
	//가는 길에 B가 있는 경우
	if(nrx==bx&&nry==by)
	blue=rmove;
	//가는 길에 구멍이 있는 경우
	if(mat[nrx][nry]=='O')
	rex=rmove;
	nrx+=dx[i];
	nry+=dy[i];
	}
	bool bex=false;
	bool red=false;
	int nbx, nby;
	int bmove=0;
	nbx=bx+dx[i];
	nby=by+dy[i];
	while(mat[nbx][nby]!='#'){
	bmove++;
	//가는 길에 R이 있는 경우
	if(nbx==rx&&nby==ry)
	red=true;
	//가는 길에 구멍이 있는 경우
	if(mat[nbx][nby]=='O')
	bex=true;
	nbx+=dx[i];
	nby+=dy[i];
	}
	//서로 같은 직선상에 없는 경우
	if(!blue&&!red){
	if(rex){
	ans=cnt+1;
	goto print;
	}
	else if(bex){
	continue;
	}
	else{
	q.push({cnt+1, rx+dx[i]*rmove, ry+dy[i]*rmove, bx+dx[i]*bmove, by+dy[i]*bmove});
	}
	}
	//R이 가는 길에 B가 있는 경우
	else if(blue){
	//구멍이 B보다 앞쪽에 있는 경우 하나 빼야댐
	if(rex){
	if(rex<blue){
	ans=cnt+1;
	goto print;
	}
	continue;
	}
	else{
	rmove--;
	q.push({cnt+1, rx+dx[i]*rmove, ry+dy[i]*rmove, bx+dx[i]*bmove, by+dy[i]*bmove});
	}
	}
	//B가 가는 길에 R이 있는 경우
	else{
	if(rex){
	continue;
	}
	else{
	bmove--;
	q.push({cnt+1, rx+dx[i]*rmove, ry+dy[i]*rmove, bx+dx[i]*bmove, by+dy[i]*bmove});
	}
	}
	}
	}
	print:
	printf("%d\n", ans);
	return 0;
	}

view raw 13460.cpp hosted with ❤ by GitHub