백준 13460 구슬탈출2 - 구현 자체가 너무 까다로운 bfs문제 c++

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

13460번: 구슬 탈출 2

진짜 코드도 길고, 구현도 까다로운 문제다.

삼성 sw역량테스트 기출문제라길래, 평소에 풀어야지 풀어야지 하다가 오늘 날잡고 풀어봤는데 꽤나 어려웠다.

아니 솔직히 solved.ac 골드3 수준은 아닌거 같다 ㅠㅠ 

 

코드 설명

https://na982.tistory.com/82?category=145346 이블로그를 보고 참고해서 풀었다.

-우선 메인함수는 입력받아서 bfs돌리는 것 밖에 없으니까 설명은 스킵.

INFO라는 구조체를 만들었다.

빨간구슬 파란구슬, 그리고 몇번 이동했는지에 대한 정보를 담고 있는 구조체임.

처음에 입력받을때 초기 구조체를 메인함수에서 만들어서, 큐에 넣는다.

그후 전형적인 네방향 탐색을 하는데, next_bx by rx ry라는 변수를 만든다.

그 후에 4방향 탐색을 진행하게 되는데, 지금 밟고 있는 위치가 #이나 O가 아니면 방향대로 계속 나아가고, 

#이면 왔던 방향 거꾸로 한번 나아간다. 벽위에 구슬이 밟고 있을 수는 없기 때문이다.

그다음에, 빨간구슬과 파란 구슬이 같은 좌표상에 있을 경우를 예외처리 해준다.

빨간구슬, 파란 구슬 중 더 많이 움직인 구슬을 찾아서, 그 구슬이 이동한 방향대로 한번 빼주면 된다.

 

맨처음에 이걸 어떻게 구현하지 생각했을땐 참 까마득하다. 실제 저 배열을 가지고 글자 R과 B를 직접적으로 물리적으로 옮기려고 애쓴거 같은데, 구조체를 이용하면 훨씬 쉽게 풀수 있다.

 

다음에 이 문제는 다시한번 꼭 풀어봐야 겠다. 특히 SWEA치기 전에..

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct INFO{
    int ry,rx,by,bx,count;
};
 
INFO start;
char map[11][11];
 
int bfs(){
    const int dy[4]={-1,1,0,0};
    const int dx[4]={0,0,-1,1};
    int ret=-1;
    int visited[10][10][10][10]={0,};
    queue<INFO> q;
    q.push(start);
    visited[start.ry][start.rx][start.by][start.bx]=1;
    while(!q.empty()){
        INFO cur = q.front();
        q.pop();
        if(cur.count>10) break;
        if(map[cur.ry][cur.rx]=='O' && map[cur.by][cur.bx]!='O') {//최적값찾은경우
            ret = cur.count;
            break;
        }
 
        for(int dir=0; dir<4; dir++){
            int next_ry = cur.ry;
            int next_rx = cur.rx;
            int next_by = cur.by;
            int next_bx = cur.bx;
 
            while (1) {
                if (map[next_ry][next_rx] != '#' && map[next_ry][next_rx] != 'O') {
                    next_ry += dy[dir], next_rx += dx[dir];
                }
                else {
                    if (map[next_ry][next_rx] == '#') {
                        next_ry -= dy[dir], next_rx -= dx[dir];
                    }
                    break;
                }
            }
 
            while (1) {
                if (map[next_by][next_bx] != '#' && map[next_by][next_bx] != 'O') {
                    next_by += dy[dir], next_bx += dx[dir];
                }
                else {
                    if (map[next_by][next_bx] == '#') {
                        next_by -= dy[dir], next_bx -= dx[dir];
                    }
                    break;
                }
            }
 
 
            if(next_rx==next_bx && next_ry==next_by){ //같은위치일때 처리.
                if(map[next_ry][next_rx]!='O'){ //구멍에 동시에 빠지면 -1 return 하면됨.
                    int red_dist = abs(next_ry - cur.ry)+abs(next_rx-cur.rx);
                    int blue_dist = abs(next_by - cur.by)+abs(next_bx-cur.bx);
                    if(red_dist>blue_dist){
                            next_ry-=dy[dir];
                            next_rx-=dx[dir];
                    }
                    else{
                            next_by-=dy[dir];
                            next_bx-=dx[dir];
                    }
                }
            }
            if(visited[next_ry][next_rx][next_by][next_bx]==0){
                visited[next_ry][next_rx][next_by][next_bx]=1;
                INFO next;
                next.ry = next_ry;
                next.rx = next_rx;
                next.by = next_by;
                next.bx = next_bx;
                next.count = cur.count+1;
                q.push(next);
            }
        }
 
    }
    return ret;
}
 
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0; i<n;i++)
        cin>>map[i];
    for(int i=0; i<n;i++){
        for(int j=0; j<m; j++){
            if(map[i][j]=='R'){
                start.ry = i;
                start.rx = j;
            }
            if(map[i][j]=='B'){
                start.by=i;
                start.bx=j;
            }
        }
    }
    start.count=0;
    cout<<bfs();
}