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

문제

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

13460번: 구슬 탈출 2

접근방법

삼성 sw역량평가에 출제됐던 문제라고한다.

 

푸는 방법은 대충 bfs 이용해서 하는 거 같은데, 

코드가 복잡해지니까 나중에는 디버깅이 잘 안되서 많이 헤멨다. 그래서 유투브를 참고했다. 

링크 : https://www.youtube.com/watch?v=SarTy3ZwmVo&t=1114s&ab_channel=na982

 

내가 생각했던 풀이보다 훨씬 간결했다.

특히 인상깊었던 점은 visited를 쓸 생각을 못했는데, visited를 4차원 배열로 선언해서 구슬이 왔던 방향으로 되돌아가는 걸 방지했다는 점이다.

 

그리고 공의 이동방법에 대해서도 해답을 못찾고 있었는데, 나는 아예 맵 전체를 queue에 담아볼까라는 생각도 했었다.

왜냐하면, 구슬의 위치가 하나도 아니고 빨간 공과 파란 공을 함께 움직여야할 뿐더러, 빨간 구슬과 파란 구슬이 곂치지 않도록 해야하는 조건도 있기 때문에, 구슬의 위치만 queue에 넣어서 풀기가 어려워 보였다.

 

요약하면, 구슬이 되돌아가지 않도록 하는 것과 구슬이 중첩되지 않도록 하는 것.

이 두가지를 처리하는 것이 어려웠다.

 

구슬이 되돌아가지 않도록 하는 문제는 visited를 만들어 처리했고, 

중첩되지 않도록 하는 문제는 만약 구슬이 중첩된 경우 더 많은 거리를 이동한 구슬을 한 칸 뒤로 보내서 해결했다.

 

구슬을 한 칸 뒤로 보내는 문제는 dy[i]와 dx[i]를 하나씩 빼줌으로 해결했다.

 

dy와 dx 배열을 이용해서 구슬의 이동을 구현하는 것도 내가 생각하지 못했던 부분이다.

나는 while문을 이용해 다음 경로가 '.'인 경우, 이동하도록 구현하려고 했지만, 생각해보니 'B' 'R'인 경우도 이동할 수 있어야했고,

이를 위해서 'B', 'R'을 지도상에서 지워야하나 어쩌나를 고민했었다. 하지만 '#'과 'O'인 경우빼고 다 이동하는 걸로 구현하면 되는 문제였다. 어쨌든, dy와 dx 배열을 이용해서 짧은 코드로 좌 우 위 아래 모두 구슬을 굴릴 수 있었다.

 

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <cmath>

using namespace std;

#define FOR(i, n) for(int i=0;i<n;i++) 
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define MAX 987654321

struct Ball{
    int ry, rx, by, bx;
    int count;
};
const int dy[] = {0, 0, -1, 1};     //left, right, up, down
const int dx[] = {-1, 1, 0, 0};

vector<vector<char>> board;
bool visited[10][10][10][10] = {0,};
int N, M;
Ball start;

int bfs() {
    queue<Ball> q;
    q.push(start);
    visited[start.ry][start.rx][start.by][start.bx] = 1;
    int ret =  -1;
    while(!q.empty()) {
        Ball b = q.front();
        q.pop();
        if (b.count > 10) break;

        if (board[b.ry][b.rx] == 'O' && board[b.by][b.bx] != 'O') {
            ret = b.count;
            break;
        } else if (board[b.by][b.bx] == 'O') continue;

        FOR(i, 4) {
            int nextry = b.ry;
            int nextrx = b.rx;
            int nextby = b.by;
            int nextbx = b.bx;
            
            //빨간 공 이동.
            while(board[nextry + dy[i]][nextrx + dx[i]] != '#') {
                nextry += dy[i]; nextrx += dx[i];
                if (board[nextry][nextrx] == 'O') break;
            }
            //파란 공 이동.
            while(board[nextby + dy[i]][nextbx + dx[i]] != '#') {
                nextby += dy[i]; nextbx += dx[i];
                if (board[nextby][nextbx] == 'O') break;
            }
            //옮긴 결과 위취가 곂친 경우
            if (nextry == nextby && nextrx == nextbx && board[nextry][nextrx] != 'O') {
                //공은 한쪽으로만 움직임. 더 많이 움직인 쪽이 뒤로감.
                int red_dist = abs(nextry - b.ry) + abs(nextrx - b.rx);
                int blue_dist = abs(nextby - b.by) + abs(nextbx - b.bx);
                if (red_dist > blue_dist) {
                    nextry -= dy[i]; nextrx -= dx[i];
                } else {
                    nextby -= dy[i]; nextbx -= dx[i];
                }
            }
            if (!visited[nextry][nextrx][nextby][nextbx]) {
                visited[nextry][nextrx][nextby][nextbx] = 1;
                Ball next;
                next.ry = nextry;
                next.rx = nextrx;
                next.by = nextby;
                next.bx = nextbx;
                next.count = b.count + 1;
                q.push(next);
            }
        }
    }
    return ret;
}

int main() {
    FASTIO
    cin >> N >> M;
    board = vector<vector<char>>(N, vector<char>(M));
    FOR(i, N) FOR(j,M) {
        cin >> board[i][j];
        if (board[i][j] == 'R') {
            start.ry = i;
            start.rx = j;
        } else if (board[i][j] == 'B') {
            start.by = i;
            start.bx = j;
        }
    }
    start.count = 0;
    int ret = bfs();
    cout << ret << endl;
    return 0;
}

개선할 점

구슬을 끝까지 굴리는 방법.

구슬 두개를 동시에 굴리는 방법.

4차원 visited 배열을 이용하는 방법.

구슬이 중첩되지 않게 중첩된 경우 더 먼거리를 이동한 구슬을 한 칸 뒤로 이동시키는 방법.

많은 것들을 배웠다. 

 

다음에 비슷한 상황을 만나면 잘 써먹도록 하자.