BAEKJOON 구슬 탈출 1~3

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

13459번: 구슬 탈출

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

13460번: 구슬 탈출 2

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

15644번: 구슬 탈출 3

3 문제 모두 백트래킹으로 해결할 수 있다. (구슬 탈출 4는 안돼는 것으로 알고 있다.)

 

15644번: 구슬 탈출 3에서는 간만에 골프를 쳐봤다.

만약에 풀이에 실패해서 이 블로그를 봤고, 게시판의 테스트 데이터를 전부 넣어봤지만 정확한 답이 나온다면, 필자와 같은 이유로 고생하고 있을 수 있기에 한가지 경우를 주자면

 

3 10
##########
#.O...R.B#
##########

나는 이런 경우를 제대로 확인하지 않았다. 예제 7을 약간 변형한 것이라지만 도움이 될 수 있을것이라 생각한다.

 

 

좀 더 자세한 풀이를 구체화 하자면 위, 아래, 왼쪽, 오른쪽으로 기울이는 모든 경우에 대해 빨간 공과 파란 공을 움직일 수 있을 때 까지 한 방향으로 움직여야 한다. 만약 두 공이 겹치는 상황이라면 두 공중 하나만 움직이고 하나는 움직이지 말아야 한다. 또한, 공의 위치가 구멍의 위치가 같아졌을 때도 움직이지 말아야 한다. 그리고 두 공중 하나가 구멍에 들어갔을 때 다음과 같은 케이스를 생각할 수 있다.

1.	빨간 공이 구멍의 좌표로 이동했고, 파란 공을 이동시키면 구멍의 좌표로 도달한다.
2.	빨간 공이 구멍의 좌표로 이동했고, 파란 공의 이동 방향은 벽쪽이며, 벽에 닿은 상태이다.
3.	파란 공이 구멍의 좌표로 이동했다.

여기서 1 과 3 의 상황에서는 해당 탐색을 그만두고 패기하여야 하며, 2 의 상황에서는 탐색을 중단하고 성공했다는 표식을 Return 해주면 된다. 만약 위 구멍의 좌표로 이동한 공이 없다면 탐색을 계속해야 한다.

 

아래는 13459번: 구슬 탈출의 정답 코드이다.

 

#include <bits/stdc++.h>
using namespace std;
int i,j;
int N,M,dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
char A[13][13];
int f(int x,int y,int X,int Y,int cnt){
    int ret=2e9;
    if(cnt>10)return ret;
    for(int k=0;k<4;k++){
        int nx=x,ny=y,nX=X,nY=Y;
        bool flag=true,nxt=true;
        while(flag){
            flag=false;
            char n1=A[nx+dx[k]][ny+dy[k]],n2=A[nX+dx[k]][nY+dy[k]];
            if((n1=='.'||n1=='O')&&A[nx][ny]!='O'&&(nx+dx[k]!=nX||ny+dy[k]!=nY)){
                nx+=dx[k];
                ny+=dy[k];
                flag=true;
            }
            if((n2=='.'||n2=='O')&&A[nX][nY]!='O'&&(nX+dx[k]!=nx||nY+dy[k]!=ny)){
                nX+=dx[k];
                nY+=dy[k];
                flag=true;
            }
            n1=A[nx][ny];n2=A[nX][nY];
            if(n1=='O'&&n2!='O'&&A[nX+dx[k]][nY+dy[k]]=='#')return 1;
            else if(n2=='O'||(n1=='O'&&A[nX+dx[k]][nY+dy[k]]=='O'))nxt=false;
        }
        if(nxt)ret=min(ret,f(nx,ny,nX,nY,cnt+1)+1);
    }
    return ret;
}
int main(){
    cin>>N>>M;
    int x,y,X,Y;
    for(i=1;i<=N;i++){
        for(j=1;j<=M;j++){
            cin>>A[i][j];
            if(A[i][j]=='R'){
                A[i][j]='.';
                x=i,y=j;
            }
            if(A[i][j]=='B'){
                A[i][j]='.';
                X=i,Y=j;
            }
        }
    }
    int ans=f(x,y,X,Y,0);
    cout<<(ans<=10);
    return 0;
}