[Algorithms] 백준 13460번 구슬 탈출 2

백준 13460번 구슬 탈출 2

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

 

문제 풀이

해당 문제는 bfs 느낌보다 dfs 느낌으로 접근하여 진행함 !!!!!!!!

1. 보드

    - 크기 NxM (세로 N, 가로 M)

    - 가장 바깥 행과 열은 막혀져 있음.

    - 구멍이 하나 있음.

        - 입력 데이터 "O"

    - 상, 하, 좌, 우 4가지 방향으로 기울이기 가능함. (최대 10회)

 

2. 빨간 구슬

    - 구멍에 들어가야 함.

    - 입력 데이터 "R"

 

3. 파란 구슬

    - 절대 구멍에 들어가선 안됨.

    - 입력 데이터 "B"

 

 

주의 사항

1. 보드를 기울이면 파란 구슬과 빨간 구슬이 동시에 움직임

  → 파란 구슬을 끝까지 이동시킨 후 빨간 구슬을 끝까지 이동시킨다 (X)

  → 파란 구슬과 빨간 구슬을 동시에 1칸씩 이동시키며 끝까지 이동시킨다 (O)

 

2. 각 구슬을 1칸씩 동시에 이동시키기 때문에, 이동에 관해서 정확한 로직이 필요함.

  → 빨간 구슬이 구멍에 들어간 후, 파란 구슬을 이동시킬 때 빨간 구슬은 이미 없어서 다른 값으로 세팅해야 함.

  → 한 구슬이 이동하다 벽에 막혔을 때, 이동시키지 않아야 함.

  → 백준의 예제 입력 7을 한번 알아보자.

          위의 예제에서 보드를 왼쪽으로 기울이면, 빨간 구슬이 먼저 들어간다. 이 때, 저장하고 있는 빨간 구슬 값을

          초기화하지 않으면, 파란 구슬도 들어갈 수 있는 상황에서 진행이 안됨.

 

3. 현재 코드 DFS의 특성상 다양한 return 등 조건이 필요함.

   → dfs의 특성상 조건에 맞지 않는 과정은 return을 잘해야 됨.

   → 최대 기울이기 횟수가 10회 이기 때문에, 10회가 넘으면 return.

   → 현재 최소 값보다 기울이기 횟수를 같거나 많이 진행했다면 return.

   → 파란 구슬이 Hole에 빠졌다면 무조건 return.

   → 이전에 기울였던 방향값을 챙겨서 해당 방향의 반대로 진행하는 것을 방지(for문 내 contine)

       → 예를 들어, 현재 턴에서 위쪽으로 기울였다면 다음 턴에서 아래쪽으로 기울이지 않도록 함.

 

 

 

#include <iostream>
#include <stdio.h>
#include <queue>
#include <vector>
 
using namespace std;
 
struct Point {
    int x;
    int y;
    Point() : x(0), y(0) {};
    Point(int x, int y) : x(x), y(y) {};
};
 
int N, M;
Point redOrigin, blueOrigin, holeOrigin;
int map[11][11];
 
int dx[4] = { 1,0,-1, 0 };
int dy[4] = { 0, 1, 0 ,-1 };
 
int answer = 11;
 
bool comparePoint(Point t1, Point t2) {
    if (t1.x == t2.x && t1.y == t2.y) return true;
    return false;
}
 
void dfs(Point redPos, Point bluePos, int cnt, int dir) {
    bool isRedHole = comparePoint(redPos, holeOrigin);
    bool isBlueHole = comparePoint(bluePos, holeOrigin);
    if (cnt > 10 || cnt >= answer || isBlueHole) return;
    if (isRedHole) {
        if (answer > cnt) answer = cnt;
        return;
    }
 
 
    int cxR, cyR;
    int cxB, cyB;
    for (int i = 0; i < 4; i++) {
        if (dir != -1 && (dir + 2) % 4 == i) continue;
        bool isRedStop = false;
        Point redNext = redPos;
        Point redTemp;
 
        bool isBlueStop = false;
        Point blueNext = bluePos;
        Point blueTemp;
        while (1) {
            if (!isRedStop) {
                cxR = redNext.x + dx[i];
                cyR = redNext.y + dy[i];
                redTemp = Point(cxR, cyR);
                if (cxR < 0 || cyR < 0 || cxR >= N || cyR >= M) {
                    isRedStop = true;
                    redTemp = redNext;
                }
                else {
                    if (map[cxR][cyR] == 1) {
                        isRedStop = true;
                        redTemp = redNext;
                    }
                }
            }
            if (!isBlueStop) {
                cxB = blueNext.x + dx[i];
                cyB = blueNext.y + dy[i];
                blueTemp = Point(cxB, cyB);
                if (cxB < 0 || cyB < 0 || cxB >= N || cyB >= M) {
                    isBlueStop = true;
                }
                else {
                    if (map[cxB][cyB] == 1) {
                        isBlueStop = true;
                        blueTemp = blueNext;
                    }
                }
            }
            if (comparePoint(redTemp, blueTemp)) {
                isRedStop = true;
                isBlueStop = true;
            }
 
            if (!isRedStop) {
                if (map[cxR][cyR] == 0) {
                    redNext = redTemp;
                }
                else if (map[cxR][cyR] == 1) {
                    isRedStop = true;
                }
                else if (map[cxR][cyR] == 2) {
                    redNext = redTemp;
                    redTemp = Point(-1, -1);
                    isRedStop = true;
                }
                else if (comparePoint(redTemp, blueTemp)) {
                    isRedStop = isBlueStop = true;
                }
            }
 
            if (!isBlueStop) {
                if (map[cxB][cyB] == 0) {
                    blueNext = blueTemp;
                }
                else if (map[cxB][cyB] == 1) {
                    isBlueStop = true;
                }
                else if (map[cxB][cyB] == 2) {
                    blueNext = blueTemp;
                    blueTemp = Point(-1, -1);
                    isBlueStop = true;
                }
                else if (comparePoint(redTemp, blueTemp)) {
                    isRedStop = isBlueStop = true;
                }
            }
 
            // check hole-in
            if (isRedStop && isBlueStop) break;
        }
        if (comparePoint(redPos, redNext) && comparePoint(bluePos, blueNext)) continue;
        dfs(redNext, blueNext, cnt + 1, i);
    }
}
 
int main()
{
    char t;
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            map[i][j] = 0;
            if (i == 4) {
                i = i;
            }
            cin >> t;
            if (t == '#') {
                map[i][j] = 1;
            }
            else if (t == 'B') {
                blueOrigin = Point(i, j);
            }
            else if (t == 'R') {
                redOrigin = Point(i, j);
            }
            else if (t == 'O') {
                holeOrigin = Point(i, j);
                map[i][j] = 2;
            }
        }
    }
 
    dfs(redOrigin, blueOrigin, 0, -1);
    if (answer > 10) {
        cout << "-1";
    }
    else {
        cout << answer;
    }
    return 0;
}