백준 알고리즘 풀이 13460번 - 구슬 탈출 2

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

13460번: 구슬 탈출 2

---

삼성 코테에 기출되었던 문제.

- bfs 문제

 

알고리즘

---

1. 현재 파란 구슬의 좌표와, 빨간 구슬의 좌표를 queue에 넣는다.

2. queue에서 하나 꺼내서, 이동할수 있는 경로로 이동한다. 이때, 다음 방문할 좌표가 벽이거나, 구멍을 만나거나, 맵의 사이즈에 맞지않는 다면, 이동을 중지한다. ans를 1더해준다. 이동후 좌표가 이미 방문한 곳이라면, continue.

3. ans가 10보다 큰 경우 -1을 리턴하고 종료한다.

4. 만약 두 공이 겹쳐있는경우, 이동거리가 긴걸 한칸 전으로 이동시킨다. 만약 파란공이 O으로 들어간경우, continue. 파란공은 들어가지 않고, 빨간 공만 들어간 경우 ans를 리턴하고 종료. 

5. queue에 현재 빨간공의 좌표, 파란공의 좌표, ans를 넣어준다. 넣어준 좌표를 방문한 좌표로 등록한다.

6. 2-5번을 반복.

시간 복잡도

---

맵을 입력받는 시간복잡도 : O(N * M) 

bfs 시간복잡도 : O(N+M) 

이동에 소요되는 시간복잡도 : O(N)

따라서 총 시간복잡도 : O(N*M)

소스코드

---

#include <cstdio>
#include <iostream>
#include <queue>

using namespace std;

char map[15][15];
int isVisited[15][15][15][15];
struct bead{
    int rx,ry,bx,by,count;
};
const int dx[6] = {0,0,0,1,-1};
const int dy[6] = {0,1,-1,0,0};
int sizeX, sizeY;
queue<bead> q;

void move(int &x, int &y, int &c, int dx, int dy) {
    // 다음 방문할 곳이 벽이거나, O이거나 방문할 좌표가 1보다 크거나 같거나 맵사이즈보다 크다면 넣지않음.
    while (map[y+dy][x+dx] != '#' && map[y][x] != 'O' && y+dy<=sizeY && x+dx>=1 && y+dy>=1 && x+dx<=sizeX) {
        x += dx;
        y += dy;
        c += 1;
    }
}

int bfs(){
    while(!q.empty()){
        bead a= q.front();
        int blueX = a.bx;
        int blueY = a.by;
        int redX = a.rx;
        int redY = a.ry;
        int ans = a.count;
        q.pop();
        ans ++;
        // 움직인 횟수가 10보다 크면 종료
        if(ans>10) {
            break;
        }
        for(int i=1;i<=4;i++){
            int rc=0, bc =0;
            int nextBlueX=blueX, nextBlueY=blueY,nextRedX=redX,nextRedY=redY;
            move(nextRedX,nextRedY,rc,dx[i],dy[i]);
            move(nextBlueX,nextBlueY,bc,dx[i],dy[i]);
            // 파란공이 빠진 경우
            if(map[nextBlueY][nextBlueX]=='O'){
                continue;
            }
            // 빨간 공이 빠진 경우
            if(map[nextRedY][nextRedX]=='O'){
                return ans;    
            }
            // 두 구슬이 겹치는 경우, 이동한것이 더 긴 경우를 뒤로 이동시킨다.
            if(nextBlueX == nextRedX && nextBlueY==nextRedY){
                if(rc>bc){
                    // rc를 뒤로 이동시킨다.
                    nextRedX = nextRedX - dx[i];
                    nextRedY = nextRedY - dy[i];
                }
                else{
                    nextBlueX = nextBlueX - dx[i];
                    nextBlueY = nextBlueY - dy[i];
                }
            }
            // 이미 방문한 곳이라면 큐에 넣지 않는다.
            if(isVisited[nextRedX][nextRedY][nextBlueX][nextBlueY]){
                continue;
            }
            // 아니라면, 큐에 넣고 visited로 체크
            isVisited[nextRedX][nextRedY][nextBlueX][nextBlueY] = true;
            q.push({nextRedX,nextRedY,nextBlueX,nextBlueY,ans});
        }
    }
    return -1;
}
int main()
{
    int rx, ry,bx, by;
    cin>>sizeY>>sizeX;
    for(int y=1;y<=sizeY;y++){
        for(int x=1;x<=sizeX;x++){
            cin>>map[y][x];
            if(map[y][x]=='R'){
                rx  = x;
                ry =y;
            }
            else if(map[y][x]=='B'){
                bx = x;
                by = y;
            }
        }
    }
    q.push({rx,ry,bx,by,0});
    isVisited[rx][ry][bx][by]=true;
    int ans = bfs();
    cout<<ans;
}

 

 

틀린 내용이나 지적 언제나 환영입니다.

도움이 되었다면 하트 한번씩 눌러주세요:)