[삼성 기출 문제] 백준 13460 구슬 탈출 2

문제 링크

클릭시 문제로 이동합니다.

어떻게 풀까?

우선, 맵의 크기를 확인해 봅시다!

10 * 10의 맵의 크기를 가집니다.

그리고, 빨간 공과 파란공 2 가지 경우가 있죠.

그 말인 즉슨!

4 차원 배열을 통해서 [빨간공의 행][빨간공의 열][파란공의 행][파란공의 열] 형태로 visit 처리를 만들 수 있고,

이를 통해 bfs를 이용하면 구슬을 빼낼 수 있는 최단 시간을 출력할 수 있습니다!

큐 에는 빨간공의 위치와 파란공의 위치를 넣으면 되겠죠!

10번이 넘어가면 -1을 return 하면 되겠군요!

그럼, 판을 상, 하, 좌, 우로 움직일 땐 어떻게 하면 될까요?

그저 공의 위치를 저장해 놓고, 오른쪽으로 이동하면서 벽이 만나는 경우 그 전의 위치에다가 공을 위치시키기만 하면 됩니다!

아래의 경우를 보겠습니다!

자, 이 상태에서 오른쪽으로 움직이는 경우를 확인해 봅시다.

우선, 빨간 공이 오른쪽으로 이동할 수 있습니다.

마찬가지로, 오른쪽으로 2번째로도 이동할 수 있습니다.

마찬가지로, 오른쪽으로 3칸 움직일 수 있습니다!

하지만, 이제 다음으로 가면 맵을 벗어나므로, 빨간공을 벗어나기 바로 직전에 위치시킵니다.

검은색을 벽이라고 하면, 어떻게 이동할까요?

이렇게 벽을 만나면 벽 왼쪽에 공을 이동시킵니다.

그럼 이렇게 되겠죠!

그럼 이번엔 문제점에 대해서 한 번 살펴볼까요?

사람을 힘들게 하는 경우는 바로 아래 그림과 같은 경우입니다.

아래 공은 이동시키면 위치가 겹쳐버립니다!

이 경우를 해결하는 것은 생각보다 어렵지 않습니다.

바로, 공이 해당 위치로 도달하는 시간을 측정하는 것입니다.

처음에 있던 빨간공 파란공의 위치와 비교하시면, 파란공은 해당 지점으로 가는데 2초가 필요하고, 빨간공은 3초가 필요합니다.

  

더 늦게 도착하는 녀석을 한칸 뒤로 빼면, 공을 아주 적절하게 위치시킬 수 있습니다!

이렇게, bfs를 이용해서 카운트를 구하다가,

빨간공이 홀에 빠지는 순간에 리턴을 해주면 됩니다!

파란색 공이 빠지면 무조건 안되므로, 이 경우는 다음 큐에 넣지 않는것! 잊지마세요!

코드

#include<queue>
 
using namespace std;
char map[10][11];
int m, n;
 
struct COD {
    int br, bc;
    int rr, rc;
};
 
COD st;
bool visit[10][10][10][10];
 
int dr[4] = { -1,1,0,0 };
int dc[4] = { 0,0,-1,1 };
 
int bfs() {
    queue<COD> que;
    visit[st.br][st.bc][st.rr][st.rc] = true;
    int time = 0;
    bool escape = false;
 
    que.push(st);
 
    while (que.size()) {
        int cnt = que.size();
 
        while (cnt--) {
            COD now = que.front();
            que.pop();
 
            if (map[now.rr][now.rc] == 'O') { escape = true; break; }
 
            for (int d = 0; d < 4; d++) {
                bool out[2] = { false,false };
                int t[2] = {};
                int p[2][2] = { { now.br, now.bc }, {now.rr, now.rc} };
 
                for (int i = 0; i < 2; i++) {
                    while(map[p[i][0]+dr[d]][p[i][1]+dc[d]] !='#'){
                        t[i]++;
                        p[i][0] = p[i][0] + dr[d];
                        p[i][1] = p[i][1] + dc[d];
                        if (map[p[i][0]][p[i][1]] == 'O') break;
                    }
                    out[i] = map[p[i][0]][p[i][1]] == 'O';
                }
 
                if (out[0]) continue;
                
                if (p[0][0] == p[1][0] && p[0][1] == p[1][1]) {
                    if (t[0] > t[1]) p[0][0] -= dr[d], p[0][1] -= dc[d];
                    else p[1][0] -= dr[d], p[1][1] -= dc[d];
                }
                
                if (visit[p[0][0]][p[0][1]][p[1][0]][p[1][1]]) continue;
                visit[p[0][0]][p[0][1]][p[1][0]][p[1][1]] = true;
                
                COD next = { p[0][0], p[0][1], p[1][0], p[1][1] };
                que.push(next);
            }
        }
        if (escape) break;
        time++;
 
        if (time > 10) break;
    }
    return escape ? time : -1;
}
 
int main() {
    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] == 'R') {
                st.rr = i;
                st.rc = j;
                map[i][j] = '.';
            }
            else if (map[i][j] == 'B') {
                st.br = i;
                st.bc = j;
                map[i][j] = '.';
            }
        }
    }
 
    cout << bfs();
 
    return 0;
}
 
 

시간복잡도

시간복잡도는 visit개수 만큼이겠죠!입니다.