그냥 간단한 dfs/bfs 문제이다. dfs로 풀어도 되겠지만 10번 이하로 구슬을 빼내야 하는 조건이 있길래 bfs로 풀어봤다.
#include<stdio.h>
#include<queue>
using namespace std;
int board[100][100]; //.은 0, #는 1, O는2
int N,M;
int ans = 0;
struct state{
int rx,ry,bx,by,num;
};
int wx[4]={0,0,1,-1};
int wy[4]={1,-1,0,0};
queue<state>escape;
state mov(int i, state curr)
{
int bc=0,rc=0;
while(board[curr.bx][curr.by]==0)
{
curr.bx+=wx[i];
curr.by+=wy[i];
bc++;
}
while(board[curr.rx][curr.ry]==0)
{
curr.rx+=wx[i];
curr.ry+=wy[i];
rc++;
}
if(board[curr.bx][curr.by]==2)
{
return {-1,-1,-1,-1,-1};
}
else if(board[curr.rx][curr.ry]==2)
{
return {-2,-2,-2,-2,curr.num+1};
}
else if(curr.rx==curr.bx && curr.ry==curr.by)
{
if(rc>bc)
{
curr.rx-=wx[i];
curr.ry-=wy[i];
}
else
{
curr.bx-=wx[i];
curr.by-=wy[i];
}
}
curr.rx-=wx[i];
curr.ry-=wy[i];
curr.bx-=wx[i];
curr.by-=wy[i];
curr.num++;
return curr;
}
void bfs()
{
int flag = 0;
while(!escape.empty() && flag == 0)
{
state x = escape.front();
//printf("%d %d %d %d\n",x.bx,x.by,x.rx,x.ry);
escape.pop();
if(x.num>=10) continue;
for(int i=0;i<4;i++)
{
state res = mov(i,x);
if(res.rx==-1)
{
continue;
}
if(res.rx==-2)
{
flag=1;
ans=res.num;
break;
}
else
{
escape.push(res);
}
}
}
if(flag==0)
{
ans = -1;
}
return;
}
int main()
{
int frx,fry,fbx,fby;
scanf("%d %d",&N,&M);
for(int i=1;i<=N;i++)
{
for(int j=1;j<=M;j++)
{
char t;
scanf(" %c",&t);
if(t=='#') board[i][j]=1;
if(t=='.') board[i][j]=0;
if(t=='O') board[i][j]=2;
if(t=='R')
{
board[i][j]=0;
frx=i;fry=j;
}
if(t=='B')
{
board[i][j]=0;
fbx=i;fby=j;
}
}
}
escape.push({frx,fry,fbx,fby,0});
bfs();
printf("%d",ans);
}해결 코드이다.
간단하긴 한데 구현이 좀 복잡했던 거 같다.
특히 구멍에 동시에 들어가는 경우랑 구슬을 옮기는 과정 구현이 좀 복잡한데, 동시에 들어가면 더 이동을 많이 한 구슬을 왔던 방향으로 한칸 되돌리는 식으로 해결을 했다.
생각보다 구현이 복잡해서 디버깅을 오래 해야 할 줄 알았는데 의외로 입출력 예제를 한번에 다 통과했다.
근데 제출했을 때 자꾸 틀려서 뭐가 문젠지 좀 헤맸는데 bfs과정에서 x.num>10일 때 continue를 시켰었는데
x.num이 10일 때 그 밑의 과정들을 수행하게 되면 결국 x.num이 11일 때도 11을 답으로 출력하기 때문에 안된다.
이 부분을 고치니까 바로 해결됐다.
풀이 자체는 바로 알았는데 구현 연습을 하는데 도움이 되는 좋은 문제였다.
