백준 15644 - 구슬 탈출 3(C++)

문제 링크입니다 https://www.acmicpc.net/problem/15644

15644번: 구슬 탈출 3

 

https://junseok.tistory.com/60

백준 13460 - 구슬 탈출 2(C++, 복습)

백준 13460 - 구슬 탈출 2에서 문자열이 추가된 문제 입니다! 구슬 탈출 2를 풀지 않았다면, 먼저 풀고 오면 좋겠습니다!

 

문제 조건

출력 예시

빨간 구슬과 파란 구슬을 동시에 움직이는 것을 구현하고 움직임을 string으로 저장하는 것이 핵심입니다!

 

문제 접근 방법

 

1. 처음 빨강, 파랑 구슬의 위치를 저장한다.

2. 빨간 구슬의 위치에서 상,하,좌,우에서 갈 수 있는 곳을 찾는다. -> 이부분이 구슬 탈출2와 다릅니다.

3. 빨간 구슬과 파란 구슬을 움직인다. 이때 파란 구슬이 구멍에 들어간다면 해당 방향은 가지 않는 것으로 처리한다.

4. 이동이 끝난 뒤, 끝난 좌표를 큐에 넣어준뒤, 다시 BFS를 시작한다.

 

구슬의 움직임을 저장하는 구조체를 만들었습니다. 이를 큐에 담아서 정보를 저장했습니다!

typedef struct qu {
    string route;
    int cost;
    int red_x, red_y, blue_x, blue_y;
}qu;
queue<qu> ball;

 

문제 접근 방법 - 1번

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> map[i][j];
            if (map[i][j] == 'R') {
                red.first = i;
                red.second = j;
                map[i][j] = '.';
            }
            if (map[i][j] == 'B') {
                blue.first = i;
                blue.second = j;
                map[i][j] = '.';
            }
        }
    }
    visit[red.first][red.second][blue.first][blue.second] = 1;
    ball.push({ "" ,0,red.first,red.second,blue.first,blue.second });

구슬의 위치를 받은 후, map에서 갈 수 있는 공간으로 처리했습니다. 좌표를 기억하고 있기에 map에서 없애준 뒤, 길로 만들어도 괜찮습니다.

처음의 좌표에서는 이동하지 않았기에 문자열에 아무것도 넣어주지 않았습니다!

 

 

문제 접근 방법 - 2번

void find_way() {
    while (!ball.empty()) {
        qu bead = ball.front();
        ball.pop();
        if (bead.cost > 10) {
            break;
        }
        if (map[bead.red_x][bead.red_y] == 'O') {
            answer_route = bead.route;
            answer = bead.cost;
            break;
        }
        for (int i = 0; i < 4; i++) {
            if(i == 0)
                move_ball(bead.red_x, bead.red_y, bead.blue_x, bead.blue_y, i, bead.cost, bead.route + 'D');
            else if (i == 1)
                move_ball(bead.red_x, bead.red_y, bead.blue_x, bead.blue_y, i, bead.cost, bead.route + 'R');
            else if (i == 2)
                move_ball(bead.red_x, bead.red_y, bead.blue_x, bead.blue_y, i, bead.cost, bead.route + 'U');
            else if (i == 3)
                move_ball(bead.red_x, bead.red_y, bead.blue_x, bead.blue_y, i, bead.cost, bead.route + 'L');
        }
    }
}

 queue ball에는 지금까지 이동 횟수, 빨강, 파랑 구슬의 위치를 저장했습니다.

빨간 구슬의 위치가 구멍이라면, 이동 횟수를 저장하고 BFS를 마무리했습니다. 혹은 이동 횟수가 10회 초과라면 BFS를 끝냈습니다. 4방향에 따라서 D,R,U,L을 각각 넣었습니다. 

문자열에서 + '문자' 를 통해서 문자열을 늘릴 수 있습니다!

구슬의 움직임을 구현하는 move_ball() 함수에 좌표들을 넣어줘서 실행해줬습니다

 

 

문제 접근 방법 - 3번

void move_ball(int rx, int ry, int bx, int by, int way, int cost, string route) {
    red_new.first = rx;
    red_new.second = ry;
    blue_new.first = bx;
    blue_new.second = by;
    while (1) {
        red_new.first += dx[way];
        red_new.second += dy[way];
        if (map[red_new.first][red_new.second] == 'O') {
            break;
        }
        if (map[red_new.first][red_new.second] == '#') {
            red_new.first -= dx[way];
            red_new.second -= dy[way];
            break;
        }
    }
    while (1) {
        blue_new.first += dx[way];
        blue_new.second += dy[way];
        if (map[blue_new.first][blue_new.second] == 'O') {
            return;
        }
        if (map[blue_new.first][blue_new.second] == '#') {
            blue_new.first -= dx[way];
            blue_new.second -= dy[way];
            break;
        }
    }
    if (red_new.first == blue_new.first && red_new.second == blue_new.second) {
        if (get_distance(rx, ry, bx, by, red_new.first, red_new.second, blue_new.first, blue_new.second)) {
            blue_new.first -= dx[way];
            blue_new.second -= dy[way];
        }
        else {
            red_new.first -= dx[way];
            red_new.second -= dy[way];
        }
    }
    if (visit[red_new.first][red_new.second][blue_new.first][blue_new.second] == 0) {
        visit[red_new.first][red_new.second][blue_new.first][blue_new.second] = 1;
        ball.push({ route, cost + 1, red_new.first,red_new.second,blue_new.first,blue_new.second });
    }
}

빨간 구슬과 파란 구슬이 해당 방향에서 조건에 맞을 때까지 움직여줬습니다.

구슬마다 경우의 수가 3가지가 나올 수 있습니다.

1. 빨간 구슬이 구멍에 도착했을 경우 -> 해당 위치를 저장하고 구슬의 움직임을 멈춥니다.

2. 빨간 구슬이 벽에 도달했을 경우 -> 벽의 위치에서 이동 방향을 한번 빼준 위치를 저장한뒤, 멈춥니다

3. 1번, 2번 경우가 아닐 경우 -> 해당 방향으로 계속 이동합니다.

 

1. 파랑 구슬이 구멍에 도착했을 경우 -> 해당 방향이 원하는 방향이 아니기에 함수를 바로 끝내줍니다.

2. 파랑 구슬이 벽에 도달했을 경우 -> 벽의 위치에서 이동 방향을 한번 빼준 위치를 저장한뒤, 멈춥니다

3. 1번, 2번 경우가 아닐 경우 -> 해당 방향으로 계속 이동합니다.

 

이동이 끝난 뒤에는, 두 구슬의 위치가 같은지를 확인해야 합니다. 

같은 방향으로 움직였는데, 이동 횟수가 적다? -> "해당 구슬이 더 앞에 있다" 라는 의미입니다. 이를 통해서 구슬의 위치를 찾았습니다.

이동이 끝난 뒤에 도달한 위치가 전에 방문한 곳이 아니라면? -> 이를 큐에 넣어주고 해당 좌표에서 BFS를 다시 시작합니다.

 

 

자세한 것은 코드를 참고해주세요!

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#include <vector>
using namespace std;

int N, M, answer;
string answer_route;
char map[11][11];
int visit[11][11][11][11];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
pair<int, int> red, blue;
pair<int, int> red_new, blue_new;
typedef struct qu {
    string route;
    int cost;
    int red_x, red_y, blue_x, blue_y;
}qu;
queue<qu> ball;

bool get_distance(int rx, int ry, int bx, int by, int rX, int rY, int bX, int bY) {
    int red_distance = abs(rx - rX) + abs(ry - rY);
    int blue_distance = abs(bx - bX) + abs(by - bY);
    if (red_distance < blue_distance) return true;
    return false;
}

void move_ball(int rx, int ry, int bx, int by, int way, int cost, string route) {
    red_new.first = rx;
    red_new.second = ry;
    blue_new.first = bx;
    blue_new.second = by;
    while (1) {
        red_new.first += dx[way];
        red_new.second += dy[way];
        if (map[red_new.first][red_new.second] == 'O') {
            break;
        }
        if (map[red_new.first][red_new.second] == '#') {
            red_new.first -= dx[way];
            red_new.second -= dy[way];
            break;
        }
    }
    while (1) {
        blue_new.first += dx[way];
        blue_new.second += dy[way];
        if (map[blue_new.first][blue_new.second] == 'O') {
            return;
        }
        if (map[blue_new.first][blue_new.second] == '#') {
            blue_new.first -= dx[way];
            blue_new.second -= dy[way];
            break;
        }
    }
    if (red_new.first == blue_new.first && red_new.second == blue_new.second) {
        if (get_distance(rx, ry, bx, by, red_new.first, red_new.second, blue_new.first, blue_new.second)) {
            blue_new.first -= dx[way];
            blue_new.second -= dy[way];
        }
        else {
            red_new.first -= dx[way];
            red_new.second -= dy[way];
        }
    }
    if (visit[red_new.first][red_new.second][blue_new.first][blue_new.second] == 0) {
        visit[red_new.first][red_new.second][blue_new.first][blue_new.second] = 1;
        ball.push({ route, cost + 1, red_new.first,red_new.second,blue_new.first,blue_new.second });
    }
}

void find_way() {
    while (!ball.empty()) {
        qu bead = ball.front();
        ball.pop();
        if (bead.cost > 10) {
            break;
        }
        if (map[bead.red_x][bead.red_y] == 'O') {
            answer_route = bead.route;
            answer = bead.cost;
            break;
        }
        for (int i = 0; i < 4; i++) {
            if(i == 0)
                move_ball(bead.red_x, bead.red_y, bead.blue_x, bead.blue_y, i, bead.cost, bead.route + 'D');
            else if (i == 1)
                move_ball(bead.red_x, bead.red_y, bead.blue_x, bead.blue_y, i, bead.cost, bead.route + 'R');
            else if (i == 2)
                move_ball(bead.red_x, bead.red_y, bead.blue_x, bead.blue_y, i, bead.cost, bead.route + 'U');
            else if (i == 3)
                move_ball(bead.red_x, bead.red_y, bead.blue_x, bead.blue_y, i, bead.cost, bead.route + 'L');
        }
    }
}

void solve() {
    find_way();
    if (answer == 0) cout << "-1";
    else {
        cout << answer << "\n";
        cout << answer_route;
    }
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> map[i][j];
            if (map[i][j] == 'R') {
                red.first = i;
                red.second = j;
                map[i][j] = '.';
            }
            if (map[i][j] == 'B') {
                blue.first = i;
                blue.second = j;
                map[i][j] = '.';
            }
        }
    }
    visit[red.first][red.second][blue.first][blue.second] = 1;
    ball.push({ "" ,0,red.first,red.second,blue.first,blue.second });
    solve();
    return 0;
}

 

질문 및 조언 댓글 남겨주세요!