[백준/BOJ] 13460번 구슬 탈출 2 (C++)

www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

 

풀이

 

 DFS와 BFS 둘다 이용해서 풀이가 가능한 문제입니다.

 

해당 문제의 핵심이라고 생각하는 부분은 빨간 구슬과 파란 구슬의 이동에 따른 방문 여부를 확인하기 위해서 배열을 4차원으로 선언한다는 점과 이동하는 과정에서 두 구슬이 겹칠 때의 처리라고 생각합니다.

 

void move(int &nx, int &ny, int dx, int dy, int &d) {
    while(map[nx+dx][ny+dy]!='#') {
        nx+=dx;
        ny+=dy; 
        d++;
        if(map[nx][ny]=='O') break; // 이동 후 현재 위치가 구멍 안이면 이동 종료 
    }
} 
 
 ....
 
 // 빨간 구슬 이동
 move(nrx,nry,dx[i],dy[i],rd);
 // 파란 구슬 이동
 move(nbx,nby,dx[i],dy[i],bd);

 

두 구슬이 한곳에 겹칠 때의 처리를 해주기 위해서 빨간 구슬이 움직이는 거리를 저장할 변수 rd와 파란 구슬이 움직이는 거리인 변수 bd를 선언하고, move라는 함수에 인자값으로 각 구슬의 현재 좌표, 이동 방향 좌표, 구슬의 거리를 넘겨줍니다. (move는 구슬의 이동을 구현한 함수입니다.)

 

 // 현재 구슬의 위치가 구멍에 있지 않고, 겹쳐있는 경우
 if(map[nrx][nry]!='O' && map[nbx][nby]!='O' && nrx==nbx && nry==nby) {
 	if(rd>bd) {
 		nrx-=dx[i];
 		nry-=dy[i];
	 } else {
		 nbx-=dx[i];
 		nby-=dy[i];
	 }
 }

 

그러고 나서 현재 각 구슬의 좌표를 비교하여 같은 경우, 각 구슬의 이동거리를 비교합니다. 이동거리가 많은 쪽이 또 다른 구슬보다 뒤에 있었다는 것을 의미하므로 현재 좌표에서 방금 이동했었던 방향으로 한칸 뒤로 가게끔 구현했습니다.

 

전체 코드

 

/* 13460번 구슬 탈출2 (DFS) */

#include <iostream>
#include <vector>
using namespace std;

int n,m,res=2147000000;
char map[11][11];
bool visit[11][11][11][11];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

void move(int &nx, int &ny, int dx, int dy, int &d) {
    while(map[nx+dx][ny+dy]!='#') {
        nx+=dx;
        ny+=dy; 
        d++;
        if(map[nx][ny]=='O') break; // 이동 후 현재 위치가 구멍 안이면 이동 종료 
    }
}

void DFS(int rx, int ry, int bx, int by, int cnt) {
    // 현재 최소값보다 시도 수가 많은 경우
    if(res<=cnt) return;
    // 10번보다 더 움직이는 경우
    if(cnt>10) return;
    // 빨간 구슬과 파란 구슬이 모두 구멍에 들어간 경우
    if(map[rx][ry]=='O' && map[bx][by]=='O') return;
    // 파란 구슬이 구멍에 들어간 경우
    if(map[bx][by]=='O') return;
    // 빨간 구슬이 구멍에 들어간 경우
    if(map[rx][ry]=='O') {
        res=min(res,cnt);
        return;
    }
    for(int i=0;i<4;i++) {
        int nrx=rx, nry=ry, rd=0;
        int nbx=bx, nby=by, bd=0;
        // 빨간 구슬 이동
        move(nrx,nry,dx[i],dy[i],rd);
        // 파란 구슬 이동
        move(nbx,nby,dx[i],dy[i],bd);
        // 현재 구슬의 위치가 구멍에 있지 않고, 겹쳐있는 경우
        if(map[nrx][nry]!='O' && map[nbx][nby]!='O' && nrx==nbx && nry==nby) {
            if(rd>bd) {
                nrx-=dx[i];
                nry-=dy[i];
            } else {
                nbx-=dx[i];
                nby-=dy[i];
            }
        }
        if(!visit[nrx][nry][nbx][nby]) {
            visit[nrx][nry][nbx][nby]=true;
            DFS(nrx,nry,nbx,nby,cnt+1);
            visit[nrx][nry][nbx][nby]=false;
        }
    }
    
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int rx,ry,bx,by;
    cin>>n>>m;
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            cin>>map[i][j];
            // 빨간 구슬과 파란 구슬의 위치 좌표를 저장
            if(map[i][j]=='B') {
                bx=i, by=j;
            } else if(map[i][j]=='R') {
                rx=i, ry=j;
            }
        }
    }
    visit[rx][ry][bx][by]=true;
    DFS(rx,ry,bx,by,0); // 각 구슬의 좌표, 이동 시도 수
    if(res==2147000000) cout<<"-1";
    else cout<<res;
}

 

/* 13460번 구슬 탈출 2 (BFS) */

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

char map[11][11];
bool visit[11][11][11][11];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

struct State {
    int rx,ry,bx,by,cnt;
    State(int a, int b, int c, int d, int e) {
        rx=a;
        ry=b;
        bx=c;
        by=d;
        cnt=e;
    }
};

void move(int &nx, int &ny, int dx, int dy, int &d) {
    while(map[nx][ny]!='O' && map[nx+dx][ny+dy]!='#') {
        nx+=dx;
        ny+=dy;
        d++;
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int r,c,rx,ry,bx,by,cnt;
    cin>>r>>c;
    queue<State> Q;
    for(int i=0;i<r;i++) {
        for(int j=0;j<c;j++) {
            cin>>map[i][j];
            if(map[i][j]=='R') {
                rx=i, ry=j;
            } else if(map[i][j]=='B') {
                bx=i, by=j;
            }
        }
    }
    visit[rx][ry][bx][by]=true;
    Q.push(State(rx,ry,bx,by,0));
    while(!Q.empty()) {
        rx=Q.front().rx;
        ry=Q.front().ry;
        bx=Q.front().bx;
        by=Q.front().by;
        cnt=Q.front().cnt;
        Q.pop();
        // cnt가 10일때 11번째 시도이므로 종료
        if(cnt==10) break;
        for(int i=0;i<4;i++) {
            int nrx=rx, nry=ry;
            int nbx=bx, nby=by;
            int ncnt=cnt+1, rd=0, bd=0;
            // 빨간 구슬 이동
            move(nrx,nry,dx[i],dy[i],rd);
            // 파란 구슬 이동
            move(nbx,nby,dx[i],dy[i],bd);
            // 파란 구슬이 구멍에 들어갔을 때
            if(map[nbx][nby]=='O') continue;
            // 빨간 구슬이 구멍에 들어갔을 때
            if(map[nrx][nry]=='O') {
                cout<<ncnt;
                exit(0);
            }
            // 두 구슬 좌표가 같을 때
            if(nrx==nbx && nry==nby) {
                if(rd>bd) {
                    nrx-=dx[i];
                    nry-=dy[i];
                } else {
                    nbx-=dx[i];
                    nby-=dy[i];
                }
            }
            // 이미 방문한 곳일 때
            if(visit[nrx][nry][nbx][nby]) continue;
            visit[nrx][nry][nbx][nby]=true;
            Q.push(State(nrx,nry,nbx,nby,ncnt));
        }
    }
    cout<<"-1";
}