[백준/c++] 13460

https://www.acmicpc.net/submit/13460/50422153

https://na982.tistory.com/82?category=145346
해당 블로그 참조해서 풀었습니다!

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

char map[11][11]; //map에 문자가 들어가기 때문에 문자열 끝자리에 널 들어가는거 생각해서 할당

struct INFO
{
    int rx,ry,bx,by,count; //rx,y 는 빨간공 좌표 / bx,y 는 파란공 좌표
};

INFO start;

int bfs(){

    //방향 설정
    int dy[4]={-1,1,0,0};
    int dx[4]={0,0,-1,1};
    //방문기록
    int visited[10][10][10][10]={0,};

    //INFO 인자 큐를 생성해주고 시작점을 추가해줌
    queue<INFO> q;
    q.push(start);

    //시작 위치 설정해줌
    visited[start.ry][start.rx][start.by][start.bx]=1;

    //정답 카운트 설정
    //-1로 하는 이유는 10번이상이 넘는 경우 -1을 출력하므로
    int ans=-1;

    while(!q.empty()){

        // 현재 위치 설정
        INFO cur=q.front(); 
        q.pop();

       // 카운트가 10번을 넘을 경우 -1 출력
       if(cur.count > 10)
            break;

        // 빨간공은 구멍에 빠지고 파란공은 구멍에 빠지지 않은 경우
        if(map[cur.ry][cur.rx]=='O' && map[cur.by][cur.bx]!='O'){
            ans=cur.count;
            break;
        }

        // 총 4방향으로 움직이기 때문에 4번 반복
        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]!='O' && map[next_ry][next_rx]!='#'){
                    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]!='O' && map[next_by][next_bx]!='#'){
                    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_ry==next_by && next_rx==next_bx){

                if(map[next_ry][next_rx] != 'O'){
                    //이동거리를 측정한다.
                    int r_dist= abs(next_rx-cur.rx)+abs(next_ry-cur.ry);
                    int b_dist= abs(next_bx-cur.bx)+abs(next_by-cur.by);

                    //이동한 거리가 더 많은 경우가 더 뒤쪽에 있었던 경우이므로 위치를 한칸 땡겨준다.
                    if(r_dist > b_dist){
                        next_rx-=dx[dir];
                        next_ry-=dy[dir];
                    }
                    else{
                        next_bx-=dx[dir];
                        next_by-=dy[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.rx=next_rx;
                next.ry=next_ry;
                next.by=next_by;
                next.bx=next_bx;
                next.count=cur.count+1;
                q.push(next);

            }
        }

    }

    return ans;

}

int main(){
    int n,m;

    cin >> n >> m;

    for(int i=0;i<n;i++){
        cin >> map[i];
    }

    // 빨간공 파란공 현재 좌표
    for(int y=0; y<n; y++){
        for(int x=0; x<m; x++){
            if(map[y][x]=='R'){
                start.rx=x; 
                start.ry=y;
            }
            if(map[y][x]=='B'){
                start.bx=x; 
                start.by=y;
            }
        }
    }

    start.count=0;

    cout << bfs();

    return 0;
}

고찰: 두 공이 같은 위치 일때 구멍인지 아닌지 판별해주어야 합니다.