13460 구슬 탈출2

13460 구슬 탈출 2 > 2024KB, 28ms

BFS로 풀어볼 것

 

내가 푼 방법 : 

• 기본적으로 DFS로 풀었음
• 상하좌우 DFS 반복해주되 만약 그 방향으로 했을 때 공이 움직이지 않았다면 그 방향은 제외해주고 DFS (while_cnt)
• 공만 움직이고 map은 그대로이기 때문에 map은 그대로 놔두고 빨간공과 파란공의 위치만 저장하고 복사함
  • 처음에는 map 모두 복사했다가 시간초과
• 간단한 로직
  • 상하좌우 DFS 들어감
  • 빨간 공 움직이고 파란 공 움직임
  • 각 움직임은 함수로 구현했는데 0 : 안움직 안들어감, 1 : 움직 안들어감, 2 : 움직 들어감을 뜻함
  • 만약 둘 다 안움직였으면 한 차례가 끝난 것이고 파란색이 들어갔으면 종료, 빨간색이 들어갔으면 빨간색은 이제 안 움직인다고 생각하고 파란색을 움직임. 여기서 파란색이 들어가면 종료, 파란색이 안들어가면 움직인 최솟값이랑 비교해서 갱신 시켜줌

 

=> 다른 사람들에 비해 느리고 메모리 많이 먹음.

 

#include <iostream>
#include <string>

#define MAX 10
using namespace std;

typedef struct r {
    int y, x;
}R;

typedef struct b {
    int y, x;
}B;

int result = 100;
int N, M;
string map[MAX];
R ori_r;
B ori_b;

int dy[4] = { -1, 1, 0, 0 }, dx[4] = { 0,0,-1,1 };

void input() {
    cin >> N >> M;

    for (int i = 0; i < N; i++)
        cin >> map[i];
   
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 'R') {
                ori_r.y = i; ori_r.x = j;
                map[i][j] = '.';
            }
            if (map[i][j] == 'B') {
                ori_b.y = i; ori_b.x = j;
                map[i][j] = '.';
            }
        }
}

int red_move(int dir, R& r_ori, B& b_ori) {
    int new_y, new_x;
    int b_y = b_ori.y, b_x = b_ori.x, r_y = r_ori.y, r_x = r_ori.x;
    new_y = r_y + dy[dir]; new_x = r_x + dx[dir];
    while (map[new_y][new_x] == '.' && !(new_y == b_y && new_x == b_x)) { 
        new_y += dy[dir]; new_x += dx[dir]; 
    }

    switch (map[new_y][new_x]) {
    case 'O':
        r_ori.y = -1, r_ori.x = -1;
        return 2;
    case '#':
        if (new_y - dy[dir] == r_y && new_x - dx[dir] == r_x)
            return 0;
        else {
            r_ori = { new_y - dy[dir], new_x - dx[dir] };
            return 1;
        }
    case '.':
        if (new_y - dy[dir] == r_y && new_x - dx[dir] == r_x)
            return 0;
        else {
            r_ori = { new_y - dy[dir], new_x - dx[dir] };
            return 1;
        }
    }
}

int blue_move(int dir, R &r_ori, B &b_ori) {
    int new_y, new_x;
    int b_y = b_ori.y, b_x = b_ori.x, r_y = r_ori.y, r_x = r_ori.x;
    new_y = b_y + dy[dir]; new_x = b_x + dx[dir];
    while (map[new_y][new_x] == '.' && !(new_y == r_y && new_x == r_x)) {
        new_y += dy[dir]; new_x += dx[dir];
    }

    switch (map[new_y][new_x]) {
    case 'O':
        b_ori.y = -1, b_ori.x = -1;
        return 2;
    case '#':
        if (new_y - dy[dir] == b_y && new_x - dx[dir] == b_x)
            return 0;
        else {
            b_ori = { new_y - dy[dir], new_x - dx[dir] };
            return 1;
        }
    case '.':
        if (new_y - dy[dir] == b_y && new_x - dx[dir] == b_x)
            return 0;
        else {
            b_ori = { new_y - dy[dir], new_x - dx[dir] };
            return 1;
        }
    }
}

void DFS(int dir, int cnt, R r_ori, B b_ori) {
    if (cnt == 11) return;

    R r_copy = { r_ori.y, r_ori.x };
    B b_copy = { b_ori.y, b_ori.x };

    int red_result = red_move(dir, r_copy, b_copy);
    int blue_result = blue_move(dir, r_copy, b_copy);
    bool red_flag = false;
    int while_cnt = 0;
    // 0 : 안움직 안들어감, 1 : 움직 안들어감, 2 : 움직 들어감
    while (1) {
        if (red_result == 0 && blue_result == 0) break;

        if (blue_result == 2) return;
        if (red_result == 2) red_flag = true;

        if (red_flag) red_result = 0;
        else red_result = red_move(dir, r_copy, b_copy);

        blue_result = blue_move(dir, r_copy, b_copy);
        
        while_cnt++;
    }

    if (red_flag) {
        if (result > cnt) {
            result = cnt;
        }
        return;
    }
        

    for (int i = 0; i < 4; i++) {
        if (while_cnt == 0 && i == dir) continue;
        DFS(i, cnt + 1, r_copy, b_copy);
    }
        
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    input();

    for (int i = 0; i < 4; i++)
        DFS(i, 1, ori_r, ori_b);
    
    if (result == 100) cout << -1;
    else cout << result;
}