[Algorithm] 백준 13460번 : 구슬 탈출 2

 

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

13460번: 구슬 탈출 2

 

카카오 코테 풀다가 죽을 것 같아서 

삼성 코테 기출을 풀어보는데

 

^^... 삼성도 어려운데? 누가 쉽다고...... 내가 못하는건가....

 

 

* 이번 삽질

- 빨간공 움직이고 파란공 움직인 다음, 진짜 빨간공이 못움직였던게 맞는지 한번더 빨간공 확인하는 작업

- 답 리턴할 때는 continue 조건 다 지난 이후에 return

- 중복 방문이 허용되는지 잘 파악하고 check 방문 배열을 쓰자.. 이번껀 중복 되는건데 방문 했으면 못가게 해서 막힘.. 중간에 check 보긴 했는데 아 맞겟지머~~ 하고 넘어간거에.. 몇십분을 날린건지..

 

 

Code

#include <iostream>
#include <string>
#include <cstring>
#include <queue>
#include <algorithm>

using namespace std;

struct pos
{
    int redx, redy, bluex, bluey, dist, redsuccess, bluesuccess;
};

int main() {

    int n, m;
    int vv[10][10] = {0, }, check[10][10] = {0, };
    int mv[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    int redx, redy, bluex, bluey, holex, holey;
    
    cin >> n >> m;

    // v -> 0: 길, 1:막힘, 2: 빨간공, 3: 파란공, 4: 구멍
    for(int i=0; i<n; i++) {
        string tmp;
        cin >> tmp;
        for(int j=0; j<m; j++) {
            unsigned char c = tmp[j];
            if(c==(unsigned char)'.') vv[i][j] = 0;
            if(c==(unsigned char)'#') {
                vv[i][j] = 1;
            }
            if(c==(unsigned char)'R') {
                vv[i][j] = 0;
                redx = i;
                redy = j;
            }
            if(c==(unsigned char)'B') {
                vv[i][j] = 0;
                bluex = i;
                bluey = j;
            }
            if(c==(unsigned char)'O') {
                vv[i][j] = 4;
                holex = i;
                holey = j;
            }
        }
    }

    queue<pos> q;
    
    q.push({redx, redy, bluex, bluey, 0, 0, 0});

    while(!q.empty()) {
        int redx = q.front().redx, redy = q.front().redy;
        int bluex = q.front().bluex, bluey = q.front().bluey;
        int dist = q.front().dist;
        int rsuc = q.front().redsuccess, bsuc = q.front().bluesuccess;

        q.pop();

        // 파란공이 빠졌거나 이동이 10번이 넘어갔으면 이번 푸시된 큐는 무시
        if(bsuc==1 || dist == 11) continue;

        if(rsuc == 1 && bsuc == 0){
            cout << dist;
            return 0;
        }

        for(int i=0; i<4; i++) {
            int dx = mv[i][0], dy = mv[i][1];
            int rednx, redny, bluenx, blueny;
            int ndist = dist + 1;
            int redsuccess = 0, bluesuccess = 0, redstop = 0, bluestop = 0;
            int idx = 0;
            int flag = 0;

            // 계속 돌려줄 현재 보드 상태 v (이동마다 이어지지 않고 새롭게 배치할 수 있도록)
            int v[10][10] = {0, };
            memcpy(v, vv, sizeof(vv)); // 맨 처음 vv에 넣어둔 미로를 복사함

            // 복사한 곳에 현재 빨간공과 파란공 배치
            v[redx][redy] = 2;
            v[bluex][bluey] = 3;

            // 기울이기
            while(1) {

                // 빨간공 파란공 다 멈췄으면 그만 기울이기
                if(redstop && bluestop) break;

                // 빨간공 안멈췄고 성공도 못했으면 다시 움직임 (기울이기니까)
                if(!redsuccess && !redstop) {
                    // 빨간공 이동
                    if(idx == 0) {
                        rednx = redx + dx;
                        redny = redy + dy;                      
                    }
                    else {
                        rednx += dx;
                        redny += dy;
                    }

                    // 공이 지나갔으니까 길 됨
                    v[rednx-dx][redny-dy] = 0;
                    
                    /* 빨간색 공 조건 */
                    // 벽이거나 파란공이면 멈춤
                    if(v[rednx][redny]==1 || v[rednx][redny]==3) {
                        rednx -= dx;
                        redny -= dy;
                        flag = 1;
                    }

                    // 이동한 자리는 빨간공
                    v[rednx][redny] = 2;


                    // 구멍 만나면 성공 & 구멍 자리는 다시 4로 돌려놓기
                    if(rednx == holex && redny == holey) {
                        redsuccess = 1;
                        redstop = 1;
                        v[rednx][redny] = 4;                        
                    }
                }

                if(!bluesuccess && !bluestop) {
                    // 파란공 이동
                    if(idx == 0) {
                        bluenx = bluex + dx;
                        blueny = bluey + dy;
                    }
                    else {
                        bluenx += dx;
                        blueny += dy;
                    }

                    // 공이 지나갔으니까 길 됨
                    v[bluenx-dx][blueny-dy] = 0;

                    /* 파란색 공 조건 */
                    // 벽이거나 빨간공이면 멈춤
                    if(v[bluenx][blueny]==1 || v[bluenx][blueny]==2) {
                        bluenx -= dx;
                        blueny -= dy;
                        bluestop = 1;
                    }

                    // 이동한 자리는 파란공
                    v[bluenx][blueny] = 3;

                    // 구멍 만나면 성공+1
                    if(bluenx == holex && blueny == holey) {
                        bluesuccess = 1;
                        bluestop = 1;
                        v[bluenx][blueny] = 4;
                    }
                }

                /* 
                지금 위에 순서가 빨간공 움직일 수 있는지 조건 확인하고 파란공 조건 확인후 움직이는데, 
                파란공 움직인 후 정말 빨간공이 움직일 수 없던게 맞는지 한번더 움직여본다 
                ex) RB <- 이렇게 배치되어있고 오른쪽으로 이동하는 경우
                */
                if(flag) {
                    // 빨간공 이동
                    if(idx == 0) {
                        rednx = redx + dx;
                        redny = redy + dy;                      
                    }
                    else {
                        rednx += dx;
                        redny += dy;
                    }

                    // 공이 지나갔으니까 길 됨
                    v[rednx-dx][redny-dy] = 0;
                    
                    /* 빨간색 공 조건 */
                    // 벽이거나 파란공이면 멈춤
                    if(v[rednx][redny]==1 || v[rednx][redny]==3) {
                        rednx -= dx;
                        redny -= dy;
                        redstop = 1;
                    }
                    // 구멍 만나면 성공+1
                    if(rednx == holex && redny == holey) {
                        redsuccess = 1;
                        redstop = 1;
                    }

                    // 이동한 자리는 빨간공
                    v[rednx][redny] = 2;
                }
            
                idx++;
            }
    
            q.push({rednx, redny, bluenx, blueny, ndist, redsuccess, bluesuccess});
        }
    }

    cout << -1;
    return 0;
}