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

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

13460번: 구슬 탈출 2

삼성 SW 역량테스트 기출 문제입니다. 답을 알기 전에는 매우 어렵지만, 원리를 알면 쉽게 풀리는 문제였습니다.

문제 조건

출력 예시

빨간 구슬과 파란 구슬을 동시에 움직이는 것을 구현하는게 핵심입니다!

 

문제 접근 방법

 

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

2. 빨간 구슬의 위치에서 상,하,좌,우에서 갈 수 있는 곳을 찾는다.

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

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

 

 

 

문제 접근 방법 - 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] = '.';
            }
        }
    }

구슬의 위치를 받은 후, 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 = bead.cost;
            break;
        }
        for (int i = 0; i < 4; i++) {
            move_ball(bead.red_x, bead.red_y, bead.blue_x, bead.blue_y, i, bead.cost);
        }
    }
}

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

빨간 구슬의 위치가 구멍이라면, 이동 횟수를 저장하고 BFS를 마무리했습니다. 혹은 이동 횟수가 10회 초과라면 BFS를 끝냈습니다.

4방향으로 구슬이 움직일 수 있기에, 구슬들의 위치와, 이동 방향을 move_ball() 함수에 넣었습니다.

 

 

문제 접근 방법 - 3번

void move_ball(int rx, int ry, int bx, int by, int way, int cost) {
    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({ 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;
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 {
    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) {
    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({ 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 = bead.cost;
            break;
        }
        for (int i = 0; i < 4; i++) {
            move_ball(bead.red_x, bead.red_y, bead.blue_x, bead.blue_y, i, bead.cost);
        }
    }
}

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

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;
}

 

 

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