[백준 13460][C++] 구슬 탈출 2 (Gold 2)

[문제보기]

 13460. 구슬 탈출 2

13460번: 구슬 탈출 2

 

[풀이과정]

일단 빨간색 공, 파란색 공에 대한 좌표를 따로 저장해 두고 그 부분을 '.'로 만들어주었다.

그리고 4방향으로 대해 완전 탐색 알고리즘을 이용하여 공이 빠질 수 있는지를 계산해주었다.

 

전체 코드의 로직은 

1. 빨간공 움직이기

2. 파란공 움직이기

3. 구멍에 빠졌는지 확인

4. map[][]에서 두 구슬이 겹쳐있을수도 있기 때문에 검사

5. 재귀

가 된다.

 

1. 빨간공 움직이기

while()문을 사용하여 다음으로 움직이는 곳이 비어있는 곳이면 움직인다. 

'#'을 만난다면 while()문을 끝낸다.

'O"을 만난다면 Red_flag를 true로 바꿔주면서 whil()문을 끝낸다.

그리고 while()문을 끝낼 시 '#'를 만나고 끝내기 때문에 빨간 구슬의 위치를 한 칸 줄여준다.

 

2. 파란공 움직이기

1번과 동일

 

3. 구멍에 빠졌는지 확인

Red_flag, Blue_flag를 확인을 해서 구멍에 빠졌는지 확인을 하는데, 파란 구슬이 빠졌으면 재귀를  바로 끝내고,

빨간공이 빠졌으면 ans를 업데이트해주고 재귀를 끝내준다.

 

4. 구슬이 겹쳤는지 확인

각 구슬의 좌표를 검사해서 겹쳤는지 확인을 하는데, 이 부분은 두 구슬이 움직인 거리를 검사를해서 더 많이 

움직인 구슬의 위치를 한 칸 움직여서 겹쳐있는 부분을 피해준다.

 

5. 재귀

재귀를 통해 구슬을 움직여준다. 이 부분에서 자신이 왔던 방향과 그 방향의 반대방향은 의미가 없는 방향이므로 

continue로 넘어가준다.

 

[소스코드]

#include <iostream>
using namespace std;
int n ,m, ans = 987654321;
char map[10][10];
pair<int, int> Red, Blue;
pair<int, int> movdir[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int Cal_Dist(int y, int x, int yy, int xx){
    return abs(yy - y) + abs(xx - x);
}

int Inverse(int d){
    if(d == 0) return 2;
    else if(d == 1) return 3;
    else if(d == 2) return 0;
    
    return 1;
}

void DFS(int Ry, int Rx, int By, int Bx, int cnt, int dir){
    if(cnt >= ans) return;
    if(cnt > 10) return;

    bool Red_flag = false;
    bool Blue_flag = false;

    int nRy = Ry + movdir[dir].first;
    int nRx = Rx + movdir[dir].second;
    while(1){
        if(map[nRy][nRx] == '#') break;
        if(map[nRy][nRx] == 'O'){
            Red_flag = true;
            break;
        }
        nRy += movdir[dir].first;
        nRx += movdir[dir].second;
    }
    nRy -= movdir[dir].first;
    nRx -= movdir[dir].second;

    int nBy = By + movdir[dir].first;
    int nBx = Bx + movdir[dir].second;
    while(1){
        if(map[nBy][nBx] == '#') break;
        if(map[nBy][nBx] == 'O'){
            Blue_flag = true;
            break;
        }
        nBy += movdir[dir].first;
        nBx += movdir[dir].second;
    }
    nBy -= movdir[dir].first;
    nBx -= movdir[dir].second;

    if(Blue_flag) return;
    else{
        if(Red_flag){
            ans = min(ans, cnt);
            return;
        }
    }

    if(nRy == nBy && nRx == nBx){
        int Red_Dist = Cal_Dist(Ry, Rx, nRy, nRx);
        int Blue_Dist = Cal_Dist(By, Bx, nBy, nBx);
        if(Red_Dist > Blue_Dist){
            nRy -= movdir[dir].first;
            nRx -= movdir[dir].second;
        }
        else{
            nBy -= movdir[dir].first;
            nBx -= movdir[dir].second;
        }
    }

    for(int i=0; i<4; i++){
        if(i == dir) continue;
        if(i == Inverse(dir)) continue;

        DFS(nRy, nRx, nBy, nBx, cnt+1, i);
    }
}


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'){
                Red.first = i;
                Red.second = j;
                map[i][j] = '.';
            }
            else if(map[i][j] == 'B'){
                Blue.first = i;
                Blue.second = j;
                map[i][j] = '.';
            }
        }
    }

    for(int i=0; i<4; i++){
        int y = Red.first;
        int x = Red.second;

        int yy = Blue.first;
        int xx = Blue.second;   
        DFS(y, x, yy, xx, 1, i);
    }
    
    if(ans > 10 || ans == 987654321){
        cout << -1;
    }
    else{
        cout << ans;
    }
}

 

[해결 과정 중 실수한 부분]

 

얍문's Coding World 참고

yabmoons.tistory.com/229