13460번 구슬 탈출 2

삼성 SW 역량 테스트 기출문제이다.

역시나 어렵다.

삼성같은 경우 DFS, BFS와 함께 Simulation, Brute Force를 결합한 문제를 자주 출제하는 것 같다.

예전에 어떤 분 코드 참고하였는데, 그 분 블로그를 까먹었다 ㅠ

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

이 문제 풀면서 생각해야할 것.

1. visit 배열을 활용할 때, 2차원 배열로만 생각하지 말자.

   (더군다나 문제에서 공은 같이 움직이기 때문에 같이 처리해줘야한다.)

2. 수학 관련 메서드를 생각해보자. (여기에서는 abs())

3. 81번 째 줄 코드가 있는 이유는 빨간 구슬, 파란 구슬 둘 다 빠지면 탈출 실패이기 때문이다.(주석도 참고).

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int N = 0, M = 0; // 세로 = y = N, 가로 = x = M → 헷갈릴까봐 적어두는 편이다.
 
bool visit[13][13][13][13] = { false, }; // 공이 같이 움직인다. 방문 여부를 2차원 배열로만 생각하지 말자. 
 
char map[13][13]; // 전역 변수로 선언
 
int ry = 0, rx = 0, by = 0, bx = 0; // 빨간 구슬, 파란 구슬 위치
 
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, -1, 0, 1 };
 
queue<pair<pair<int, int>, pair<int, int> > > q; // ry, rx, by, bx 순
 
int BFS()
{
    q.push({ {ry, rx}, {by, bx} }); // queue에 push
 
    visit[ry][rx][by][bx] = true; // 방문 표시
 
    int ret = 0; // 답
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--) // 시간 단축
        {
            int Ry = q.front().first.first;
            int Rx = q.front().first.second;
 
            int By = q.front().second.first;
            int Bx = q.front().second.second;
 
            q.pop();
 
            if (map[Ry][Rx] == 'O' && map[Ry][Rx] != map[By][Bx]) // 문제 조건(빨간 구슬 위치 != 파란 구슬 위치)
            {
                return ret;
            }
 
            for (int i = 0; i < 4; i++)
            {
                int Red_y = Ry; int Red_x = Rx;
                int Blue_y = By; int Blue_x = Bx;
 
                while (map[Red_y + dy[i]][Red_x + dx[i]] != '#' && map[Red_y][Red_x] != 'O')
                {
                    // 다음 위치와 현재 위치를 비교하면서 while문을 실행한다.
 
                    // 구슬은 벽(#)을 통과할 수 없다.
 
                    Red_y += dy[i];
                    Red_x += dx[i];
                }
 
                while (map[Blue_y + dy[i]][Blue_x + dx[i]] != '#' && map[Blue_y][Blue_x] != 'O')
                {
                    // 다음 위치와 현재 위치를 비교하면서 while문을 실행한다.
 
                    // 구슬은 벽(#)을 통과할 수 없다.
 
                    Blue_y += dy[i];
                    Blue_x += dx[i];
                }
 
                if (Red_y == Blue_y && Red_x == Blue_x) 
                {
                    // 중력을 통해 움직였으나(위 while 2개), 그 후 빨간 구슬과 파란 구슬의 위치가 같다면,
 
                    if (map[Red_y][Red_x] == 'O') continue; 
                    // 하지만 도착한 곳이 탈출 구멍(O)이라면 무시한다.
 
                    /* 
                      이유는 밑에 if문을 통해 빨간 구슬 또는 파란 구슬의 위치가 달라지게 되는데
                        ret가 1 증가하게 되고,
                       위에서 둘 중 하나는 탈출 구멍(O)이고, 둘의 위치가 달라지므로 return 되어버린다.
                    */
 
                    if (abs(Red_y - Ry) + abs(Red_x - Rx) < abs(Blue_y - By) + abs(Blue_x - Bx))
                    {
                        /*움직인 거리가 파란 구슬이 더 많다면,
                        (= 파란 구슬보다 빨간 구슬이 더 앞 쪽에 있었다. 
                           그러나 위치가 똑같을 순 없으니 파란 구슬의 위치를 조정해야한다.)
                        */
 
                        Blue_y -= dy[i];
                        Blue_x -= dx[i];
                    }
                    else // 그게 아니라면
                    {
                        Red_y -= dy[i];
                        Red_x -= dx[i];
                    }
                }
     
                if (visit[Red_y][Red_x][Blue_y][Blue_x]) continue; // 방문 했다면 무시
 
                visit[Red_y][Red_x][Blue_y][Blue_x] = true; // 방문 표시
                 
                q.push({ {Red_y, Red_x}, {Blue_y, Blue_x} });
            }
        }
 
        if (ret >= 10) return -1; // 문제 조건
 
        ++ret;
    }
 
    return -1; // queue가 비어있다는 것은 위에서 무슨 일이 발생했다는 뜻이다.(예 : 탈출 실패)
}
 
int main(void)
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> map[i][j]; // 붙어있는 문자들을 입력 받을 때에는 cin이 편하다. scanf 사용 X
 
            if (map[i][j] == 'R')
            {
                ry = i;
                rx = j;
            }
            else if (map[i][j] == 'B')
            {
                by = i;
                bx = j;
            }
        }
    }
 
    cout << BFS() << '\n';
 
    return 0;
}