[BOJ 13460] 구슬 탈출 2 (C++)

구슬 탈출 2 (Gold 2)

문제

전체 문제 보기

13460번: 구슬 탈출 2

접근법

보드를 상하좌우 중 한번 기울일 경우 구슬들의 위치가 변합니다. 각 구슬들의 위치를 이동할 수 있는 하나의 노드로 보고 한번 기울여 이동된 구슬의 위치를 인접 노드로 생각하여 BFS로 풀 수 있습니다. BFS를 활용하여 보드를 기울일 수 있는 다양한 경우의 수 중 R만 구멍에 들어갈 수 있는 최단 거리를 구할 수 있습니다. BFS의 알고리즘의 기본적인 구조는 다음과 같습니다.

• 전체 데이터 입력
• BFS 탐색 시작
  • 시작 지점 지정
  • 시작 지점 큐에 삽입
  • 큐가 빌 때까지 아래를 반복
    • 큐의 첫 번째 원소를 빼냄
    • 첫 번째 원소의 인접 노드를 탐색
      • 목표 노드라면 탐색 성공. 탐색 종료
      • 방문하지 않은 노드라면 해당 노드 큐에 삽입
• 목표 노드를 못 찾았다면 탐색 실패

이번 문제에서도 위 구조를 활용하여 풀이할 수 있습니다. 반복문에서 인접 노드를 탐색할 시 상하좌우로 기울였을 때 구슬의 위치를 계산하여 그 위치와 깊이 값을 다시 큐에 넣는 방식으로 탐색을 진행합니다. BFS에서는 방문한 노드를 기록해야 하는데 이때는 bool 타입의 4차원 배열(R.x,R.y,B.x,B.y의 방문 위치를 저장)을 활용할 수 있습니다. 하나의 차원이 최대 10이기 때문에 4차원 배열이라도 충분히 사용 가능한 크기입니다.

그리고 보드를 기울였을 때 구슬이 멈추게될 위치는 Roll함수를 만들어 계산할 수 있습니다. 이때 주의할 점은 R이 앞에 있는지 B가 앞에 있는지에 따라서 어떤 구슬을 먼저 굴려야 할지 결정해야 한다는 것입니다. 그리고 문제에는 정확히 언급되어 있지 않지만 구슬이 구멍에 빠지게 되면 이어서 바로 뒤이어 오는 구슬도 빠질 수 있다는 점입니다. 예를 들어 아래의 경우는 R이 구멍에 빠지지만 B도 구멍에 빠지게 되기 때문에 -1이 나와야 합니다. 때문에 구멍에 빠지게 될 경우 해당 구슬의 위치를 0, 0으로 초기화해야 합니다.

######
#O.RB#
######

위 상황을 주의하여 다음과 같이 구현할 수 있습니다.

전체 구현

#include <stdio.h>
#include <vector>
#include <queue>
#include <string>
using namespace std;

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

struct Pos {
    Pos(int _y, int _x) : y(_y), x(_x) {}
    Pos() {}
    int y{};
    int x{};

};
struct Move {
    Pos R;
    Pos B;
    int depth{};
};
const int MAX = 10;
using Map = vector<string>;


// return: 구멍을 찾은 경우 true
// map: 전체 지형
// cur: 굴릴 구슬의 L-Valud
// i: 방향 인덱스
// other: 고려할 구슬이 있다면 고려해야할 구슬의 위치.(없다면 디폴트값으로 고려안함)
bool Roll(const Map& map, Pos& cur, int i, Pos other = Pos()) {

    bool FindHole{};

    Pos next;
    next.y = cur.y + dy[i];
    next.x = cur.x + dx[i];
    // 벽이 아니거나, 다른 구슬과 겹치지 않는다면 계속 굴러간다.
    while (map[next.y][next.x] != '#'
        && !((other.y == next.y) && (other.x == next.x)))
    {
        cur.x = next.x;
        cur.y = next.y;
        next.y += dy[i];
        next.x += dx[i];
            
        // 공이 구멍을 찾은 경우
        if (map[cur.y][cur.x] == 'O')
        {
            // 공을 없앤다.
            cur.x = 0;
            cur.y = 0;
            return true;
        }
    }
    return false; 
}

int BFS(const Map& map,Pos start_R, Pos start_B)
{
    bool visited[MAX][MAX][MAX][MAX]{};

    queue<Move> q;
    Move cur;

    visited[start_R.x][start_R.y][start_B.x][start_B.y] = true;
    cur.R = start_R;
    cur.B = start_B;
    cur.depth = 0;
    q.push(cur);
    while (!q.empty())
    {
        cur = q.front();
        //printf("R: (%d, %d) | B: (%d, %d) | depth: %d \n", cur.R.x, cur.R.y, cur.B.x, cur.B.y, cur.depth);
        // 10번째에도 못 찾은 경우
        if (cur.depth == 10) return -1;
        q.pop();

        for (int i = 0; i < 4; ++i)
        {
            Move next = cur;
            next.depth = cur.depth + 1;
            bool RFind{}, BFind{};
            // R을 B 보다 앞에 있는 경우
            if (next.R.y * dy[i] + next.R.x * dx[i] > next.B.y * dy[i] + next.B.x * dx[i])
            {
                // R을 먼저 굴린다.
                if (Roll(map, next.R, i)) RFind = true;
                // B를 굴린다.
                if (Roll(map, next.B, i, next.R)) BFind = true;
            }
            else
            {
                // B를 먼저 굴린다.
                if (Roll(map, next.B, i)) BFind = true;
                // R을 굴린다.
                if (Roll(map, next.R, i, next.B))RFind = true;
            }
            // B가 구멍에 들어갈 경우 아무것도 안함(해당 경로 무시)
            if (BFind)
                ;
            // R만 구멍에 들어갈 경우 탐색 깊이 반환
            else if (RFind)
                return next.depth;
            // 아무도 구멍에 들어가지 않은경우
            else
            {
                // 탐색한적 없는 경우라면 q에 삽입 후 탐색을 계속 진행함.
                if (visited[next.R.x][next.R.y][next.B.x][next.B.y] == false)
                {
                    visited[next.R.x][next.R.y][next.B.x][next.B.y] = true;
                    q.push(next);
                }
            }
        }

    }
    // 구멍을 찾지 못했다면 -1
    return -1;
}
void InputData(Map& map, int N, int M, Pos& R, Pos& B)
{
    map.resize(N);
    for (int i = 0; i < N; ++i)
    {
        char temp[MAX + 1];
        scanf("%s ", &temp);
        map[i].resize(M);
        for (int j = 0; j < M; ++j)
        {
            // R,B는 위치만 파악후 '.'으로 기록
            map[i][j] = temp[j];
            if (temp[j] == 'R')
            {
                R.x = j;
                R.y = i;
                map[i][j] = '.';
            }
            if (temp[j] == 'B')
            {
                B.x = j;
                B.y = i;
                map[i][j] = '.';
            }
        }
    }
}
int main() {
    int N, M; // (3 ≤ N, M ≤ 10)
    scanf("%d %d ", &N, &M);
    Map map;
    Pos R, B;
    
    // 데이터 입력
    InputData(map, N, M, R, B);

    //BFS
    int answer = BFS(map, R, B);

    printf("%d\n", answer);

    return 0;
}